图的关键路径 (Critical Path) 复习指南

1. 核心概念

1.1 定义

关键路径是在 AOE 网 (Activity On Edge Network) 中，从源点 (Start) 到汇点 (End) 的所有路径中，路径长度（权重之和）最长 的那条路径。

1.2 适用范围 (AOE 网)

AOE 网：
- 顶点 (Vertex)：表示 事件 (Event)，例如“项目开始”、“地基打好”。事件是一个瞬间点。
- 边 (Edge)：表示 活动 (Activity)，边上的权值表示活动持续的时间。
核心意义：关键路径的长度决定了完成整个工程所需的 最短时间。

1.3 关键活动

关键路径上的活动称为 关键活动。
这些活动是没有“缓冲时间”的，一旦延误，整个工期都会延误。

2. 核心计算步骤 (四步法)

计算关键路径通常需要计算四个核心参数。
假设图中有 $n$ 个事件（顶点），边 $$ 表示活动 $ak$，持续时间为 $w{i,j}$。

第一步：求事件的最早发生时间 $ve(k)$

顺序：从源点开始，按 拓扑序 向后推导。
逻辑：一个事件必须等它前面所有的前驱活动都结束才能发生。
公式： $ve(j) = \max \{ ve(i) + w_{i,j} \}$ （其中 $i$ 是 $j$ 的所有前驱节点。源点 $ve(start) = 0$）

第二步：求事件的最迟发生时间 $vl(k)$

顺序：从汇点开始，按 逆拓扑序 向前推导。
逻辑：为了不延误工期，该事件最晚必须在什么时候发生。
公式： $vl(i) = \min \{ vl(j) - w_{i,j} \}$ （其中 $j$ 是 $i$ 的所有后继节点。汇点初始化 $vl(end) = ve(end)$）

第三步：求活动的最早开始时间 $e(k)$

对象：针对边（活动）。
逻辑：活动 $a_k$ (边 $$) 只要起点事件 $i$ 发生了，就可以开始。
公式： $e(k) = ve(i)$

第四步：求活动的最迟开始时间 $l(k)$

对象：针对边（活动）。
逻辑：活动 $ak$ (边 $$) 必须在终点事件 $j$ 最迟发生时间之前完成，减去活动耗时 $w{i,j}$ 就是它最迟必须开始的时间。
公式： $l(k) = vl(j) - w_{i,j}$

判定标准

计算 时间余量 (Slack)：$d(k) = l(k) - e(k)$。
若 $d(k) == 0$（即 $e(k) == l(k)$），则该活动为 关键活动。
所有关键活动连接起来的路径即为 关键路径。

3. 常见题型与考法

题型一：手算关键路径 (表格法)

描述：给出一个 AOE 网，要求列出所有事件的 $ve, vl$ 和所有活动的 $e, l$，并找出关键路径。
解题技巧：

先写出拓扑序列（防止计算 $ve$ 时漏掉前驱）。
画表：
- 表1：顶点 $ve, vl$。
- 表2：边（活动） $i \to j$, 权值, $e, l, l-e$。
口诀：求 $ve$ 往后推取最大（木桶短板效应的逆向，必须全到齐）；求 $vl$ 往前推取最小（这就好比死线 DDL，必须满足最紧迫的那个）。

题型二：工程加速与工期缩短

描述：问“缩短活动 A 的时间，总工期是否缩短？”或“为了缩短工期，应该缩短哪些活动？”
核心逻辑：

只有缩短 关键活动 的时间，才有可能缩短总工期。
缩短非关键活动，工期不变（因为它有缓冲时间）。
陷阱：如果图中存在多条关键路径，必须同时缩短 所有关键路径上共有的活动，或者分别缩短每条关键路径上的活动，工期才会减少。

题型三：判断关键路径的变化

描述：改变某个权值后，关键路径是否发生改变？
注意：

当一个关键活动被缩短太多，它可能变成非关键活动，原本的非关键路径可能变成新的关键路径（“次关键路径”上位）。

4. 易错点与注意事项

⚠️ 1. AOV 与 AOE 的区别

AOV 网中，节点是动作，找拓扑序是看流程顺序。
AOE 网中，边是动作，找关键路径是看最长耗时。
考试坑点：关键路径算法依赖拓扑排序（计算 $ve$ 需要拓扑序），所以通常是一起考的。

⚠️ 2. 关键路径不唯一

一个 AOE 网可能有多条关键路径。
这些路径的长度（总耗时）一定相等。
在多条关键路径并存时，只加快其中一条路径上的某项活动，不能缩短整个工期。

⚠️ 3. 虚活动 (Dummy Activity)

表现：权值为 0 的边。
作用：为了表达逻辑依赖关系，或者解决画图时的语法冲突。
计算：计算时照常代入公式，权值为 0 即可，不要忽略它，它可能也是关键路径的一部分。

⚠️ 4. $ve$ 和 $vl$ 的初始化

$ve[start]$ 默认为 0。
$vl[end]$ 必须先算出 $ve[end]$ 后，令 $vl[end] = ve[end]$，然后才能倒推其他点。

5. 代码实现思路 (C++)

关键路径的代码比拓扑排序复杂，因为需要维护 $ve$ 和 $vl$ 数组。

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int MAXN = 100;
const int INF = 1e9;

struct Edge {
    int to;
    int weight;
};

vector<Edge> adj[MAXN]; // 邻接表
int ve[MAXN]; // 事件最早发生时间
int vl[MAXN]; // 事件最迟发生时间
int indegree[MAXN];
int n; // 顶点数

// 1. 拓扑排序并计算 ve
bool topologicalSort(stack<int>& topoStack) {
    queue<int> q;
    for(int i = 0; i < n; i++) {
        if(indegree[i] == 0) q.push(i);
        ve[i] = 0; // 初始化
    }

    int count = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        topoStack.push(u); // 保存拓扑序用于逆推
        count++;

        for(auto& edge : adj[u]) {
            int v = edge.to;
            int w = edge.weight;
            indegree[v]--;
            if(indegree[v] == 0) q.push(v);
            
            // 核心公式：ve(j) = max(ve(i) + w)
            if(ve[u] + w > ve[v]) {
                ve[v] = ve[u] + w;
            }
        }
    }
    return count == n;
}

// 2. 关键路径求解
void criticalPath() {
    stack<int> topoStack;
    if(!topologicalSort(topoStack)) {
        cout << "有环，无法求解" << endl;
        return;
    }

    // 初始化 vl，赋值为汇点的 ve
    // 注意：这里假设只有一个汇点，或者取所有点中 ve 最大的作为总工期
    int maxTime = 0;
    for(int i=0; i<n; i++) maxTime = max(maxTime, ve[i]);
    for(int i=0; i<n; i++) vl[i] = maxTime;

    // 逆拓扑序计算 vl
    while(!topoStack.empty()) {
        int u = topoStack.top();
        topoStack.pop();

        for(auto& edge : adj[u]) {
            int v = edge.to;
            int w = edge.weight;
            // 核心公式：这里因为是邻接表存的是 u->v，我们要用 v 来更新 u 的 vl 需要反向图
            // 但标准做法是在正向遍历时很难直接更新，
            // 通常做法：上面的栈是 u，我们需要遍历 u 的后继 v 来做吗？
            // 不，公式是 vl(i) = min(vl(j) - w)。
            // 所以我们需要知道 u 的后继 v。
            // 可是 u 是拓扑序出来的，栈顶是拓扑序最后的元素（汇点）。
            // 所以这里写法要注意：
            // 实际上应该是在遍历 u (前驱) 的时候，利用已经算好的 v (后继) ? 
            // 不对，逆拓扑序是从后往前的。
            // 取出 u，u 是当前比较靠后的点。
            // 我们应该用 u 去更新它的前驱？不，邻接表很难找前驱。
            // 正确做法：
            // 应该在上面拓扑排序时，不仅仅记录 stack，
            // 计算 vl 的时候，可以遍历所有边？或者建逆邻接表？
            // 简便写法：按照拓扑序逆序取出 u，遍历 u 的所有邻接点 v
            // 此时 v 的 vl 还没定？不对，逆序取出，v 肯定比 u 后，v 应该已经算好了？
            // 让我们理一下：栈顶是汇点。
            // 汇点弹出。
            // 下一个弹出的是汇点的前驱 u。此时 u 的邻居 v (汇点) 已经算好 vl 了。
            // 所以遍历 u 的邻居 v，用 vl[v] - w 来更新 vl[u]。是对的！
            
            if(vl[v] - w < vl[u]) {
                vl[u] = vl[v] - w;
            }
        }
    }

    // 输出关键活动
    cout << "关键活动: " << endl;
    for(int u = 0; u < n; u++) {
        for(auto& edge : adj[u]) {
            int v = edge.to;
            int w = edge.weight;
            
            int e = ve[u];           // 活动最早开始
            int l = vl[v] - w;       // 活动最迟开始
            
            if(e == l) {
                cout << u << " -> " << v << " (len: " << w << ")" << endl;
            }
        }
    }
}