关键活动#

关键路径上的所有活动都是关键活动，即不能拖延的活动。

=> 最早开始时间 = 最晚开始时间

算法原理#

$v_e$ : 事件的最早开始时间

$v_l$ : 事件的最晚开始时间

e : 活动的最早开始时间

l : 活动的最晚开始时间

先求点再求边

第一步：

求：$v_e$ => 拓扑排序

tep1 : $v_e$ 都为 0

tep2：$v_e$ 依次更新最耗时的路径，更新过程是拓扑排序。

第二步：

求：$v_l$ => 逆拓扑排序

tep1：$v_l$ 都为 最后的 $v_e$

tep2：$v_l$ 依次求最晚开始时间

第三步：

求 ：e, l

e = 发出该活动的 $v_e$

l = 指向该活动的 $v_l$ - 活动耗时

第四步：

关键活动即 e = l 的活动

Eg：关键路径不唯一

​ l-e：时间余量（活动可以拖延多久）

动画演示#