关键路径（AOE 网）

2026 大纲 五（四）图的基本应用 4. 关键路径（前置是《拓扑排序》，AOV 与 AOE 的对照表也在那一篇）。

工期为什么等于最长路径

AOE 网是一个带权 DAG：顶点是事件（"射入它的活动全部完成、射出它的活动可以开始"这个状态），边是活动，边权是活动的持续时间。

它比一般 DAG 多一条硬约束：

🔴 入度为 0 的顶点和出度为 0 的顶点各有且仅有一个——工程只有一个起始时刻（源点）和一个完工时刻（汇点）。AOV 网可以有多个，AOE 不行。

现在问"这项工程最短要多久"。直觉可能会说"最短当然是找最短的那条路"，但那是错的。完工的定义是"所有活动都结束"——几条并行的路径同时在推进，工程要等最慢的那条走完才算完。所以：

🔴 最短工期 = 源点到汇点的最长带权路径长度。 这条最长路径就叫关键路径。

⚠️ 这里有个反直觉的地方要坐实："最短工期"和"最长路径"这两个词看着矛盾，其实说的是同一件事——工期由最慢的那条支路决定，而你没法比它更快。

顺带一提：一般图上求最长路径是 NP-难的，但 DAG 上按拓扑序做一次线性 DP 就够了，这就是下面第一步在做的事。

先动手看一眼

加载可视化中...

盯 $ve$ 正推、$vl$ 倒推这两趟的方向差别——一趟从源点往汇点推、取 max，一趟从汇点往源点推、取 min。四个量的所有计算都从这两趟里出来。

四个量：两个在顶点上，两个在边上

符号	名称	属于	计算方式	为什么
$ve(j)$	事件 $j$ 的最早发生时间	顶点	对所有前驱 $i$ 取 max：$ve(j)=max\{ve(i)+w(i,j)\}$，初值 $ve(\text{源点})=0$	射入 $j$ 的活动要全结束，最晚的那个说了算
$vl(j)$	事件 $j$ 的最迟发生时间	顶点	对所有后继 $k$ 取 min：$vl(j)=min\{vl(k)-w(j,k)\}$，初值 $vl(\text{汇点})=ve(\text{汇点})$	不能耽误任何一个后继，最紧的说了算
$e(a)$	活动 $a$ 的最早开始时间	边	$e(a)=ve(\text{起点})$	起点事件发生后才能开工
$l(a)$	活动 $a$ 的最迟开始时间	边	$l(a)=vl(\text{终点})-w(a)$	须在终点事件最迟发生前干完
$d(a)$	时间余量	边	$d(a)=l(a)-e(a)$	🔴 $d=0$（即 $e(a)=l(a)$）就是关键活动

记住"$ve$ 等所有前驱到齐、$vl$ 迁就最赶时间的后继"这两句，就不会把 max 和 min 取反。

为什么必须先拓扑排序？ 因为算 $ve(j)$ 要求它的前驱全都算完，这就得按拓扑序正推；算 $vl(j)$ 要求它的后继全都算完，这就得按逆拓扑序倒推。这就是"拓扑排序是关键路径的基础"的确切含义。

手算的第一自检：算完 $vl$ 之后必看 $vl(\text{源点})$ 是不是 0。不是 0 就说明前面算错了，当场重查，别往下走。

算法实现

int ve[MAXV], vl[MAXV];        // 事件最早 / 最迟发生时间
int topoOrder[MAXV], topoCnt;  // 拓扑序列，第二步要倒着用

// topoSort() 就是《拓扑排序》那篇的 Kahn 算法，只多做两件事：把出队顺序记进
// topoOrder[]，并在处理弧 <u,v> 时顺手正推
//     if (ve[u] + edges[i].w > ve[v]) ve[v] = ve[u] + edges[i].w;   // 正推取 max
// 返回 0 表示有环。完整代码见下方折叠块。

void criticalPath(void) {
    if (!topoSort()) { printf("图中有环，无关键路径\n"); return; }

    int sink = topoOrder[topoCnt - 1];        // 拓扑序最后一个顶点就是汇点
    for (int i = 0; i < n; i++) vl[i] = ve[sink];  // 先全置成总工期，再由 min 压下来

    for (int idx = topoCnt - 1; idx >= 0; idx--) {          // 逆拓扑序倒推 vl[]
        int u = topoOrder[idx];
        for (int i = head[u]; i != -1; i = edges[i].next)
            if (vl[edges[i].to] - edges[i].w < vl[u])        // 倒推取 min
                vl[u] = vl[edges[i].to] - edges[i].w;
    }

    printf("工程最短工期 = %d\n", ve[sink]);
    for (int u = 0; u < n; u++)                             // e == l 即关键活动
        for (int i = head[u]; i != -1; i = edges[i].next)
            if (ve[u] == vl[edges[i].to] - edges[i].w)
                printf("关键活动 <%d, %d>\n", u, edges[i].to);
}

时间与空间都是 $O(n+e)$，与拓扑排序同阶。

缩短工期：三条结论，条条有反例

这是这一节被考得最多的地方，而且三条结论全都反直觉。

结论一：缩短非关键活动，工期一点也不会变。 它本来就有余量，缩了只是余量变大。

结论二：关键路径可能不止一条，只缩短其中一条上的活动，工期同样不变。 假设有两条并行的关键路径，你把第一条上某个活动缩短了，第二条仍然是原来那么长，工期由它顶着，纹丝不动。

🔴 要缩短工期，必须动"所有关键路径的公共关键活动"。

结论三：缩短公共关键活动有效，但有下限。 缩到某条原本的非关键路径追平时，那条路径就升级成了新的关键路径，工期就此卡死，再缩就是无效投入。

⚠️ 由此可知，"缩短任一关键活动就会缩短工期"是错的，真题把它作为错误选项放过。而反过来的那一半是对的：

🔴 延长关键活动一定延长工期。 工期是一个最大值——对"变大"敏感、对"变小"迟钝。

判两个活动能否同时进行

这是一个不那么显眼、但真题问过的考法："与活动 X 同时进行的活动可能有哪些"。

注意"可能"这个词——问的不是"必然同时"，而是"存不存在某个合法调度让两者重叠"。所以做法是比较两个活动各自的可活动时间窗能否相交。

活动 $X$ 的窗口是这样的：它最早在 $e(X)$ 开工，最迟在 $l(X)$ 开工，所以整段可能占用的区间是 $[e(X),l(X)+w(X)]$。于是判据是：

活动 $X$ 与活动 $Y$ 可能同时进行 $⟺$ $e(X)<l(Y)+w(Y)$ 且 $e(Y)<l(X)+w(X)$（两个开区间有正长度的交集）。

关键活动的窗口是锁死的：$e=l$，所以它只能占 $[e,e+w]$ 这一段，没有任何挪动余地。若题目问的正是"与某个关键活动同时进行的有哪些"，就拿这个固定区间去和其他活动的窗口比。

实操上，先把每个活动的 $e$、$l$、$w$ 列成表，再补一列 $l+w$，然后逐行套上面那个不等式即可——一行一行地比，别在图上目测。

某个活动延误了，怎么补救

真题大题的最后一问常常是这类"扰动分析"，有两种问法，做法不同：

问法一：活动 $b$ 推迟到时刻 $t$ 才开始，为保证工程不延期，$b$ 的持续时间最多是多少？

推迟一个活动的开工时刻，不改变其他任何顶点的 $ve$/$vl$（其他活动照旧）。$b$ 要不延误全局，只需在它终点事件的最迟发生时间之前干完：

$$t+w_b\le vl(b\text{ 的终点})⟹w_b\le vl(\text{终点})-t$$

一步就出来。

问法二：不改 $b$ 的持续时间，压缩哪个活动也能保证不延期？

这一问要重算。$b$ 延误后它终点事件的 $ve$ 被抬高，这个抬高会沿着后继传下去，最终看汇点的 $ve$ 超了多少。要追回这个差额，只能压缩"当前这条最长路径"上、且不是 $b$ 本身的活动——压别的路径上的活动完全没用，因为工期是由这条最长路径顶着的。

所以步骤是：① 把 $b$ 延误后的 $ve$ 重新正推一遍；② 找出此刻从源点到汇点最长的那条路径；③ 在这条路径上（除 $b$ 外）挑一个活动压缩，压缩量等于超出的时间。

topoSort 的完整代码与三处实现细节（照着敲、或想弄清两个初值为什么这样取时展开）

int topoSort(void) {           // 拓扑排序 + 正推 ve[]；返回 0 表示有环
    int queue[MAXV], front = 0, rear = 0;
    topoCnt = 0;
    memset(ve, 0, sizeof(ve));
    for (int i = 0; i < n; i++)
        if (inDeg[i] == 0) queue[rear++] = i;
    while (front < rear) {
        int u = queue[front++];
        topoOrder[topoCnt++] = u;
        for (int i = head[u]; i != -1; i = edges[i].next) {
            int v = edges[i].to, w = edges[i].w;
            if (ve[u] + w > ve[v]) ve[v] = ve[u] + w;      // 正推取 max
            if (--inDeg[v] == 0) queue[rear++] = v;
        }
    }
    return topoCnt == n;
}

• ve[] 全置 0 是对的：权值非负，源点的 $ve$ 本就是 0，其余会被 max 逐步抬到位；若允许负权（AOE 网中不会出现）就必须初始化为负无穷。
• vl[] 先全置成总工期再由 min 压下来，等价于"任何事件都不允许晚于总工期发生"；初值取得比总工期小，某些 $vl$ 会被压过头。
• head 用 $-1$ 表示空链，所以要 memset(head, -1, ...)：memset 按字节填充，$-1$ 的每个字节都是 0xFF，恰好得到全 $-1$ 的 int 数组，换成别的值就不能这样填。

七事件十活动的完整手算走查（想手动模拟一遍就展开）

活动清单（起点 → 终点，持续时间）：

活动	边	$w$	活动	边	$w$
$a_1$	$v_1\to v_2$	4	$a_6$	$v_3\to v_6$	3
$a_2$	$v_1\to v_3$	2	$a_7$	$v_4\to v_5$	2
$a_3$	$v_2\to v_4$	2	$a_8$	$v_4\to v_6$	3
$a_4$	$v_2\to v_5$	3	$a_9$	$v_5\to v_7$	1
$a_5$	$v_3\to v_4$	4	$a_{10}$	$v_6\to v_7$	4

源点是 $v_1$（入度 0），汇点是 $v_7$（出度 0），符合 AOE 网的要求。

第一步：按拓扑序正推 $ve$（取 max）。一个合法拓扑序：$v_1,v_2,v_3,v_4,v_5,v_6,v_7$：

事件	计算过程	$ve$
$v_1$	源点	0
$v_2$	$ve(1)+4=4$	4
$v_3$	$ve(1)+2=2$	2
$v_4$	$max\{ve(2)+2,ve(3)+4\}=max\{6,6\}$	6
$v_5$	$max\{ve(2)+3,ve(4)+2\}=max\{7,8\}$	8
$v_6$	$max\{ve(3)+3,ve(4)+3\}=max\{5,9\}$	9
$v_7$	$max\{ve(5)+1,ve(6)+4\}=max\{9,13\}$	13

工程最短工期 $=ve(v_7)=\mathbf{13}$。 $v_4$ 的两个前驱算出来同为 6 不是巧合：$ve$ 取 max 时出现并列，就预示着可能有多条关键路径，看到并列要打起精神。

第二步：按逆拓扑序倒推 $vl$（取 min），初始化 $vl(v_7)=ve(v_7)=13$：

事件	计算过程	$vl$
$v_7$	汇点，$=ve(7)$	13
$v_6$	$vl(7)-4=9$	9
$v_5$	$vl(7)-1=12$	12
$v_4$	$min\{vl(5)-2,vl(6)-3\}=min\{10,6\}$	6
$v_3$	$min\{vl(4)-4,vl(6)-3\}=min\{2,6\}$	2
$v_2$	$min\{vl(4)-2,vl(5)-3\}=min\{4,9\}$	4
$v_1$	$min\{vl(2)-4,vl(3)-2\}=min\{0,0\}$	0

$vl(v_1)=0$ ✓ 自检通过。

第三步：逐活动算 $e$、$l$、$d$（$e(a)=ve(\text{起点})$，$l(a)=vl(\text{终点})-w$，$d=l-e$）：

活动	边	$w$	$e=ve(\text{起})$	$l=vl(\text{终})-w$	余量 $d$	$l+w$	关键活动？
$a_1$	$v_1\to v_2$	4	0	$4-4=0$	0	4	是
$a_2$	$v_1\to v_3$	2	0	$2-2=0$	0	2	是
$a_3$	$v_2\to v_4$	2	4	$6-2=4$	0	6	是
$a_4$	$v_2\to v_5$	3	4	$12-3=9$	5	12
$a_5$	$v_3\to v_4$	4	2	$6-4=2$	0	6	是
$a_6$	$v_3\to v_6$	3	2	$9-3=6$	4	9
$a_7$	$v_4\to v_5$	2	6	$12-2=10$	4	12
$a_8$	$v_4\to v_6$	3	6	$9-3=6$	0	9	是
$a_9$	$v_5\to v_7$	1	8	$13-1=12$	4	13
$a_{10}$	$v_6\to v_7$	4	9	$13-4=9$	0	13	是

最右边多加的 $l+w$ 一列，是为了做"能否同时进行"的判断——有了它，套判据只要比两个数。

第四步：连出关键路径。关键活动 $a_1,a_2,a_3,a_5,a_8,a_{10}$ 连成了两条关键路径：

• $v_1\to v_2\to v_4\to v_6\to v_7$，长度 $4+2+3+4=13$
• $v_1\to v_3\to v_4\to v_6\to v_7$，长度 $2+4+3+4=13$

自检：两条关键路径长度必须相等（都等于总工期 13）✓；所有关键活动的 $d$ 都是 0 ✓；每条关键路径都从源点通到汇点 ✓。

顺手做几个变式：

• 余量最大的活动：查 $d$ 那一列，是 $a_4$，余量 5。
• 与 $a_8$（关键活动，占 $[6,9]$）可能同时进行的有哪些：查每个活动是否满足 $e<9$ 且 $l+w>6$。$a_4$（$e=4<9$，$l+w=12>6$）✓；$a_6$（$e=2<9$，$l+w=9>6$）✓；$a_7$（$e=6<9$，$l+w=12>6$）✓；$a_9$（$e=8<9$，$l+w=13>6$）✓。而 $a_1$（$l+w=4\ngtr 6$）✗、$a_2$（$l+w=2\ngtr 6$）✗。
• $a_1$ 推迟到时刻 2 才开始，最多能持续多久：$vl(v_2)-2=4-2=2$。

缩短工期的定量分析：六条路径长度表与逐值验算（想把三条结论算一遍就展开）

先把这张网里全部 6 条路径的长度列出来：

路径	活动序列	长度
$v_1{v}_2{v}_4{v}_6{v}_7$	$a_1,a_3,a_8,a_{10}$	13（关键）
$v_1{v}_3{v}_4{v}_6{v}_7$	$a_2,a_5,a_8,a_{10}$	13（关键）
$v_1{v}_2{v}_4{v}_5{v}_7$	$a_1,a_3,a_7,a_9$	9
$v_1{v}_3{v}_4{v}_5{v}_7$	$a_2,a_5,a_7,a_9$	9
$v_1{v}_3{v}_6{v}_7$	$a_2,a_6,a_{10}$	9
$v_1{v}_2{v}_5{v}_7$	$a_1,a_4,a_9$	8

有了这张表，三个结论就都是算出来的而不是背出来的：

结论一：缩短非关键活动，工期一点也不会变。 把 $a_4$（余量 5）从 3 缩到 1，只影响最后那条长度 8 的路径，它变成 6，最长路径仍是 13。

结论二：只缩短一条关键路径上的活动，工期同样不变。$a_1$ 只出现在第一条关键路径上。把 $a_1$ 从 4 缩到 1，第一条路径变成 10， 但第二条关键路径 $v_1{v}_3{v}_4{v}_6{v}_7$ 仍然是 13，工期纹丝不动。

结论三：缩短公共关键活动有效，但存在下限。$a_8$ 与 $a_{10}$ 同时出现在两条关键路径上。取 $a_{10}$（原为 4）来缩，缩短量记作 $\delta$。 注意 $\delta$ 有一个硬上界：活动时长不能缩成负数，所以 $0\le \delta \le 4$—— 这一条在答"最多能缩多少"时最容易被忽略。

缩短量 $\delta$	0	1	2	3	4
经过 $a_{10}$ 的两条原关键路径	13	12	11	10	9
不经过 $a_{10}$ 的路径最长者	9	9	9	9	9
实际工期	13	12	11	10	9

$\delta \le 3$ 时每缩 1 天工期就少 1 天；$\delta =4$ 时工期降到 9， 此时那两条原本长度为 9 的路径升级成了新的关键路径，工期就此卡死—— 这时哪怕把另一个公共关键活动 $a_8$ 也一并缩到 0，工期仍然是 9。

同一条路径上多个活动的余量能不能各用各的（想弄清余量到底怎么用就展开）

不可以，余量是共享的，不能相加。

$d(a)=l(a)-e(a)$ 是在"其他活动都按最早时间开始"这个前提下算出来的。走查那张网里 $a_7$ 与 $a_9$ 同在路径 $v_1{v}_2{v}_4{v}_5{v}_7$ 上，各自余量都是 4，但整条路径的总富余只有 $13-9=4$：

• 若 $a_7$ 推迟 4 天（在 $l(a_7)=10$ 开工，12 完工），$v_5$ 就被推到 12，$a_9$ 的最早开始时间随之变成 12——它的余量已经被 $a_7$ 用光，归零了。
• 此时 $a_9$ 若再推迟 4 天（16 开工、17 完工），整个工程就拖到 17，工期被延误 4 天。

所以"这条路径上有两个余量 4 的活动"不等于"这条路径可以富余 8 天"。看余量要看路径，不能逐个活动累加。

复杂度的逐项来历，以及教材里 AOE 网的邻接表长什么样

操作	时间	来历
拓扑排序 + 正推 $ve$	$O(n+e)$	每个顶点入队出队各一次，每条边处理一次
逆拓扑序倒推 $vl$	$O(n+e)$	沿记录下的拓扑序反向扫一遍，每条边再处理一次
逐活动求 $e$、$l$	$O(e)$	每条边一次 $O(1)$ 计算
总体	$\mathbf{O}\mathbf{(}\mathbf{n}\mathbf{+}\mathbf{e}\mathbf{)}$	与拓扑排序同阶

空间 $O(n+e)$：邻接表 $O(n+e)$，ve[]、vl[]、topoOrder[]、队列各 $O(n)$。

图注：左边是一个 9 事件、11 活动的 AOE 网，顶点 0 是源点（标"开始"）、顶点 8 是汇点（标"结束"）， 边上的 $a_1=6,a_2=4,\dots$ 就是各活动的持续时间。 右边是它的邻接表：顶点表的 count 列存入度（拓扑排序用）， 边结点除了终点 dest 还多了一个 dur 字段存活动时长—— 正推 $ve$ 时读的就是这个 dur。 与拓扑排序那篇的 AOV 邻接表对比：结构完全一样，只多了一个 dur 列。 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.30 一个 AOE 网络及其邻接表表示，p388

考点速记

三条结论：

1. 工期 = 源点到汇点的最长路径；$ve$ 按拓扑序正推取 max，$vl$ 按逆拓扑序倒推取 min（初值 $vl(\text{汇点})=ve(\text{汇点})$）。
2. 关键活动的判据是 $e(a)=l(a)$（余量 $d=0$）；关键路径可能不唯一。
3. 缩短工期只能动"所有关键路径的公共关键活动"，且有下限；而延长关键活动一定延长工期。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 求某个活动的最早、最迟开始时间：直接套 $e(a)=ve(\text{起点})$、$l(a)=vl(\text{终点})-w$。前提是把 $ve$、$vl$ 两趟都算完。
• 求时间余量最大的活动：列出全部活动的 $d=l-e$，取最大。这道题问过两次（一次选择、一次大题分问）。
• 加快哪些活动可以缩短工期：选项给的是一对活动，因为有两条关键路径，只加快一条上的没用。做法是先找出全部关键路径，再看哪一对能同时覆盖它们。
• AOE 网叙述的真伪判断：关键路径是"路径长度最长"的（对）还是"边数最多"的（错）；"增加任一关键活动的时间不会延长工期"（错）；"缩短任一关键活动的时间将会缩短工期"（错，这是四个选项里最迷惑的一个）。
• 由压缩存储的邻接矩阵还原图再求关键路径（大题）：先把按行优先压成一维数组的上三角还原成矩阵、画出带权有向图，再在这张图上求关键路径及其长度。
• AOE 网的四问综合大题：① 最短时间与关键活动；② 与某活动可能同时进行的活动有哪些（比时间窗 $[e,l+w]$ 是否相交）；③ 余量最大的活动及其余量；④ 扰动分析——某活动推迟到时刻 $t$ 开始，为不延期它最多能持续多久（$vl(\text{终点})-t$）；若不改它的时长，该压缩哪个活动（重算 $ve$，压当前最长路径上的）。

易错："缩短任一关键活动就能缩短工期"是错的。 关键路径可能有多条，只缩其中一条上的活动，另一条照样顶着。要缩必须动公共关键活动，而且缩到某条非关键路径追平就失效。

易错："关键路径是边数最多的路径"是错的。 是带权路径长度最长的，与边数无关。

易错：余量不能沿路径累加。 同一条路径上两个活动各有 4 的余量，不等于这条路径能富余 8——前一个用掉了，后一个就归零。

易错：$ve$ 取 max、$vl$ 取 min，别取反。 记法："$ve$ 等所有前驱到齐（最晚的说了算），$vl$ 迁就最赶时间的后继（最紧的说了算）"。算完必查 $vl(\text{源点})=0$。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p178–p179，§6.6.4： "与 AOV-网相对应的是 AOE-网 (Activity On Edge)，即以边表示活动的网。 AOE-网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。"
• 同书印刷 p179： "由于整个工程只有一个开始点和一个完成点，故在正常的情况（无环）下， 网中只有一个入度为零的点，称作源点，也只有一个出度为零的点，称作汇点"； "要估算整项工程完成的最短时间，就是要找一条从源点到汇点的带权路径长度最长的路径， 称为关键路径 (Critical Path)"； 同页给出 $ve(i)=max\{ve(k)+w_{k,i}\}$ 与 $vl(i)=min\{vl(k)-w_{i,k}\}$ 两条递推式， 并明确"求 $ve(i)$ 的值，可根据拓扑顺序从源点开始向汇点递推"、 "求出 $ve(i)$ 后，可根据逆拓扑顺序从汇点开始向源点递推，求出 $vl(i)$"。
• 同书印刷 p180： $e(i)=ve(j)$、$l(i)=vl(k)-w_{j,k}$； "显然，对于关键活动而言，$e(i)=l(i)$。对于非关键活动，$l(i)-e(i)$ 的值是该工程的期限余量， 在此范围内的适度延误不会影响整个工程的工期"； 同页给出关键路径求解的五步过程，并指出"关键路径有可能不止一条"。
• 同书印刷 p179：以图 6.28 那个 11 项活动的 AOE 网为例， "关键路径有两条……长度均为 18"，是"关键路径不唯一"的教材实例。
• 同书印刷 p178：拓扑排序算法"亦是下面讨论的求关键路径算法的基础"。

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.30，p388。

相关知识

拓扑排序（关键路径的前置；AOV 与 AOE 的对照表在那一篇）｜ DAG 描述表达式（DAG 的另一类应用）｜ BFS（正推 $ve$ 用的就是 Kahn 的队列框架）｜ Dijkstra 算法（最短与最长思路相反，对照着看更清楚）｜ 邻接表（AOE 网的标准存储，边结点需额外存持续时间）

相关文章

• 图的基本概念
• 邻接矩阵
• 邻接表
• 十字链表与邻接多重表
• 广度优先搜索（BFS）
• 深度优先搜索（DFS）
• 最小生成树：Prim
• 最小生成树：Kruskal
• BFS 求无权图最短路径
• Dijkstra 算法
• Floyd 算法
• DAG 描述表达式
• 拓扑排序

交互体验

前往完整可视化页面 →

真题练习

相关真题（6题）

2025Q4210分2022Q72分2020Q82分2019Q52分2013Q92分2011Q418分