关键路径 · 融合风（象牙 + Obsidian 入口）

速查

AOE 网中从源点到汇点的最长路径为关键路径。$ve$ 正序取 max、$vl$ 逆序取 min；$e=ve(\text{弧尾})$、$l=vl(\text{弧头})-w$；e(i)=l(i) 为关键活动。O(|V|+|E|)。

核心概念 ▾

AOE 网（Activity On Edge Network）：顶点 = 事件，边 = 活动（边权为持续时间），源点入度 0、汇点出度 0。从源点到汇点的最长路径 = 关键路径，其上的活动为关键活动。

求 ve（正向拓扑）：$ve(j) = \max_{\langle i,j\rangle \in E}\{ ve(i)+w(i,j) \}$，源点 $ve(0)=0$。
求 vl（逆向拓扑）：$vl(i) = \min_{\langle i,j\rangle \in E}\{ vl(j)-w(i,j) \}$，汇点 $vl(n-1)=ve(n-1)$。
求 e、l：设活动 $a_i$ 对应边 $\langle v_j, v_k\rangle$，$e(i)=ve(j)$，$l(i)=vl(k)-w(j,k)$。
关键活动：$e(i)=l(i)$ 者。

时间复杂度 O(|V| + |E|)。

拓扑序列 v0,v1,v2,v3,v4,v5。$ve=[0,3,4,9,9,11]$；$vl=[0,4,4,9,10,11]$。

活动	弧尾→弧头	权	e	l	l−e	关键？
a0	v0→v1	3	0	1	1	否
a1	v0→v2	4	0	0	0	✅
a2	v2→v3	5	4	4	0	✅
a3	v1→v4	6	3	4	1	否
a4	v1→v3	1	3	8	5	否
a5	v3→v5	2	9	9	0	✅
a6	v4→v5	1	9	10	1	否

结果关键活动 a1、a2、a5；关键路径 v0 → v2 → v3 → v5（工程最短工期 = 汇点 ve = 11）。

考法①求关键路径 ②求 ve / vl ③判断关键活动（e=l）④求工程最短工期（汇点 ve）。

易错清单

关键活动：e(i)=l(i)。关键路径是源点到汇点的最长路径，决定工程最短工期。

ve 如何计算？

正向拓扑：ve(j)=max{ve(i)+w(i,j)}。

vl 如何计算？

逆向拓扑：vl(i)=min{vl(j)−w(i,j)}。

如何判断关键活动？

e(i)=l(i)；e=ve(弧尾)、l=vl(弧头)−w。

关键路径是最长还是最短？

最长路径，决定工程最短工期。

AOE 网（7 活动）从源点 0 到汇点 5，求关键路径

点按钮：正序求 ve → 逆序求 vl → 判关键活动 → 显示关键路径

关键活动 a1、a2、a5（e=l）；关键路径 v0→v2→v3→v5；最短工期 = ve(汇点) = 11。