6.4.5 关键路径

AOE网中顶点表示事件、边表示活动工期。先拓扑正向计算事件最早发生时间 ve；再逆拓扑计算最迟时间 vl。活动(u,v,w)最早开始e=ve[u]，最迟开始l=vl[v]-w，e=l的活动为关键活动。

手工状态

A→B=3,A→C=2,B→D=2,C→D=4。ve: A0,B3,C2,D=max(5,6)=6。vl从D6反推B4,C2,A=min(1,0)=0。A-C、C-D余量0，是关键路径，总工期6。

结构与代码

多源多汇时可加权0的超级源/汇。关键路径可能多条；缩短某一关键活动不一定缩短总工期，因为其他关键路径可能仍决定工期。

正确性依据

ve取所有前驱完成时间最大值，保证事件等齐；vl取所有后继允许时间最小值，保证不拖延总工期。零余量活动构成至少一条源汇关键路径。

错解反馈

ve用min；vl用max；只找一条最长边；认为所有关键活动同时缩短一定同量缩短工期。

迁移训练

若存在两条长度均10的关键路径，只缩短其中一条1单位，总工期如何？答案仍可能是10，由另一条决定。