关键路径

AOV 和 AOE

顶点活动（Activity On Vector，AOV）网 是指 顶点表示活动，而 边集表示活动间优先关系 的 有向图。AOV 显然不能存在环，否则会逻辑错误。

边活动（Activity On Edge，AOE）网 是指用 带权边集表示活动，而 顶点表示事件 的 有向图，其中边权表示完成活动所需条件。

应用

一般来说，AOE 用于表示一个工程的进行过程，而工程常常可以划分为若干个子工程（即“活动”），显然 AOE 也不该有环。

对工程来说总会有一个起始时刻和结束时刻，因此 AOV 一般只有一个源点（入度为 0）和一个汇点（出度为 0）。实际情况若有多个源点或汇点，可以添加一个“超级源点”（出发连接所有源点，边权为 0）和一个“超级汇点”（汇点出发连接到它，边权为 0）。

如果 AOV 给定了各顶点活动所需要时间，则可以将 AOV 转化为 AOE：

1. 将 AOV 的顶点拆成两个顶点，表示活动的起点和终点，两个顶点使用有向边连接，边权给定
2. 原 AOV 中所有的边视为 0 权边

通常，我们会想知道一个工程需要的最短时间是多少？这就引出了 关键路径：AOE 网中最长路径，把在关键路径上的活动称为 关键活动，显然 关键活动 会影响整个工程的进度。

最长路径

根据之前学的最短路径，我们可以简单的把所有边的边权乘 -1，然后使用 Bellman-Ford 或者 SPFA 来求解最短路径，然后结果求反。

如果有正环，则最长路径不存在。但是，如果要求最长简单路径，虽然一定存在，无法通过 Bellman-Ford 等算法求解，因此 最长路径问题是 NP-Hard 问题。

最长路径问题（Longest Path Problem）：求解图的 最长简单路径。

但如果是求解有向无环图（DAG）的最长路径长度，即求解关键路径，比 BF 或 SPFA 更高效的做法。

关键路径

推导求解

求关键路径，实际上就是：求解 DAG 中最长路径。

由于关键活动是不允许拖延的活动，因此 关键活动的最早开始时间必须等于最迟开始时间。可以设置 两个数组 e[] 和 l[] 来表示活动的最早开始时间和最迟开始时间。因此求关键活动就是：e[r] == l[r] 的活动 r。

顶点即事件，会存在最早发生时间和最迟发生时间，其中最早发生时间 == 上一个活动的最早结束时间，最迟发生时间 == 下一个活动的最迟开始时间。因此设置 两个数组 ve[] 和 vl[] 来表示事件 i 的最早发生时间和最迟发生时间。

因此对 e[] 和 l[] 的求解可以转化为对 ve[] 和 vl[] 的求解，假设事件 V_i 在经过活动 a_r 之后达到时间 V_j：

1. 对活动 a_r 而言，只要在事件 V_i 最早发生时马上开始，就可以使得 a_r 的开始时间最早，因此 e[r] = ve[i]

2. 如果 l[r] 时活动 a_r 的最迟发生时间，那么 l[r] + length[r] 就是事件 V_j 最迟发生时间，因此 l[r] = vl[j] - length[r]

那么如何求出 ve[] 和 vl[] 这两个数组成为关键：

1. 假设 k 个事件 V_i1 ~ V_ik 通过相应活动 a_r1 ~ a_rk 到达事件 V_j，那么 V_j 的最早开始事件 $ve[j] = max(ve[ip] + length[rp]),\ p\in [1, k]$

   • 通过拓扑序列保证：在访问某个结点时保证它的前驱结点的 ve[] 都已计算完毕

2. 假设从事件 V_i 出发通过通过相应活动 a_r1 ~ a_rk 到达 k 个事件 V_i1 ~ V_ik，那么 V_i 的最迟发生时间 $vl[i] = min(vl[jp] - length[rp]),\ p\in [1, k]$

   • 通过逆拓扑序列（拓扑序的颠倒）保证：后继结点都已计算完毕。

具体实现

通过了上面的推导，可以给出步骤总结：先求点，再夹边：

1. 按拓扑序和逆拓扑序分别计算出各顶点（事件）的最早发生时间和最迟发生时间：

   $\left\{ \begin{aligned} &最早（拓扑序）：ve[j] = \min \limits_{i, 边i\rightarrow j存在}(ve[i] + length[i\rightarrow j]) \\ &最迟（逆拓扑序）：vl[i] = \min \limits_{j, 边i\rightarrow j存在}(vl[j] - length[i\rightarrow j]) \end{aligned} \right.$

   • 使用拓扑排序获得拓扑序和逆拓扑序（将拓扑序入栈，出栈顺序就是逆拓扑序）

2. 用上面的结果计算各边（活动）的最早开始事件和最迟开始时间：

   $\left\{ \begin{aligned} &最早：e[i\rightarrow j] = ve[i] \\ &最迟：l[i\rightarrow j] = vl[j] - length[i\rightarrow j] \end{aligned} \right.$

3. $e[i\rightarrow j] = l[i\rightarrow j]$ 就是关键活动

C++

bool topologicalSort() {
    queue<int> q;
    for (int i = 0; i < n; ++i) {
        if (inDegree[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topOrder.push(u);
        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].v;
            inDegree[v]--;
            if (inDegree[v] == 0) q.push(v);
            if (ve[u] + adj[u][i].w > ve[v]) {
                ve[v] = ve[u] + adj[u][i].w;
            }
        }
    }
    if (topOrder.size() == n) return true;
    else return false;
}

int CriticalPath() {
    memset(ve, 0, sizeof(ve));
    if (!topologicalSort()) return -1;
    // vl 初始化为汇点的 ve 值
    fill(vl, vl + n, ve[n - 1]);

    // topOrder 出栈就是逆拓扑序列
    while (!topOrder.empty()) {
        int u = topOrder.top();
        topOrder.pop();
        for (int i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].v;
            if (vl[v] - adj[u][i].w < vl[u]) {
                vl[u] = vl[v] - adj[u][i].w;
            }
        }
    }

    // 遍历邻接表所有的边，计算出 e、l
    for (int u = 0; u < n; ++u) {
        for (int i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].v, w = adj[u][i].w;
            int e = ve[u], l = ve[v] - w;
            if (e == l) {
                printf("%d -> %d\n", u, v);
            }
        }
    }

    // 返回关键路径长度，即汇点的最早开始时间
    return ve[n - 1];
}

• 若不知道汇点，因为汇点的最早开始时间最大，所有 ve[] 数组中最大的就是汇点

动态规划

令 dp[i] 表示从 i 号位出发能获得的最长路径长度，这样 dp[] 中的最大值就是关键路径长度。

那么状态转移方程为：$dp[i] = max(dp[j]+length[i \rightarrow j]\ |\ (i, j) \in E)$

• 可以使用自底向上的求法，按照逆拓扑序列来求解 dp[]
• 也可以自顶向下，递归地求解 dp[]

int DP(int i) {
    if (dp[i] > 0) return dp[i];
    for (int j = 0; j < n; ++j) {
        if (G[i][j] != INF) {
            int t = DP(j) + G[i][j];
            if (t > dp[i]) {
                dp[i] = t;
                path[i] = j;
            }
        }
    }
    return dp[i];
}

// 调用 printPath 需要先获取最大的 dp[i] 的索引值 i
void printPath(int i) {
    printf("%d", i);
    while (path[i] != -1) {
        i = path[i];
        printf(" -> %d", i);
    }
}

若固定终点，求 DAG 的最长路径：同样的 dp[] 定义，同样的状态转移方程：$dp[i] = max(dp[j]+length[i \rightarrow j]\ |\ (i, j) \in E)$。

但是，dp[] 初始化不同，因为固定了终点，所以只有 dp[T] = 0，而对其他的数值可以初始化为一个很小的负数，然后设置一个 vis[] 数组来记录是否访问过。