§06 图状结构
关键路径
AOE 网络中顶点是事件、边是活动、边权是耗时。按拓扑序算最早发生时间 ve、逆拓扑序算 最晚发生时间 vl，再比较每个活动的 e 与 l：相等者即关键活动。关键路径决定工程总工期， 其上任何活动延误都会拖慢整个工程。
关键路径
伪代码
1
procedure CriticalPath(G)
2
对 G 求拓扑序 // AOE 网必须是有向无环图
3
for each v in 拓扑序 do
4
ve[v] ← max(ve[u] + w(u, v)) // 最早发生时间
5
for each v in 逆拓扑序 do
6
vl[v] ← min(vl[u] - w(v, u)) // 最晚发生时间（汇点 vl = ve）
7
for each 活动 a = (u, v) do
8
e(a) ← ve[u]; l(a) ← vl[v] - w(a)
9
if e(a) = l(a) then a 是关键活动
10
end procedure