🏷️ 知识点：Ve与vl递推

下面关于求关键路径的说法中，不正确的是（ ）。

A. 求关键路径是以拓扑排序为基础的 B. 一个事件的最早发生时间与以该事件为始的弧的活动的最早开始时间相同 C. 一个事件的最迟发生时间是以该事件为尾的弧的活动的最迟开始时间与该活动的持续时间的差 D. 任何一个活动的持续时间的改变可能会影响关键路径的改变

正确答案：C

结论

选 C。对弧 i→j，i 确实是弧尾；事件 i 的最迟发生时间应等于所有出边活动最迟开始时间的最小值，即 vl(i)=min(vl(j)-d(i,j))。选项 C 把活动最迟开始时间又减了一次持续时间，造成多减一次 d。

推导

按拓扑序计算 ve，再按逆拓扑序计算 vl，活动的时间余量为 vl(j)-ve(i)-d(i,j)。对每条出边 i→j，活动最迟开始时间是 vl(j)-d(i,j)；事件 i 的最迟发生时间就是这些出边活动最迟开始时间的最小值，不能再减一次 d(i,j)。详见 AOE 递推。

易错点

不要把“事件最迟发生”与“某一条出边活动的最迟开始”混为一谈；有多条出边时必须对 vl(j)-d(i,j) 取最小值，也不要把持续时间多减一次。改变任一活动持续时间也可能改变 ve、vl 或关键路径集合。