关键路径算法演示（AOE网）

例图

如上图，是一个AOE网，点表示状态，边表示活动及其所需要的时间。为了求出关键路径，我们使用一下算法：

1.求出到达各个状态的最早时间（按最大计）

这个过程是要从源点开始向汇点顺推：

1. V1是源点，其最早开始时间是0。
2. V2、V3、V4最早时间分别是是6、4、5。
3. 对于V5而言，V2到V5所花费时间是6+1=7，而V3到V5所花费时间是4+1=5。我们要按最大计，也就是V5最早时间是max{7,5}=7，按最大计是因为只有活动a4和a5同时完成了，才能到达V5状态。V3到V5需要5分钟，但是此时a4活动尚未完成（7分钟），所以都不能算到达V5，故而要按最大计。
4. V6只有从V4到达，所以V6的最早完成时间是（5+2=）7。
5. 同理，V7最早完成时间是16。
6. 对于V8而言，和V5处理方法一致。V8=max{V5+7,V6+4}={7+7,7+4}=14。
7. V9可算出是18。

这样，我们可以得到各个状态的最早时间的表：

最早时间表

2.求出到达各个状态的最晚时间（按最小计）

这个过程是要从汇点开始向源点逆推：

1. V9完成时间为18，最V7最迟开始时间是（18-2=）16

   

   逆推

   
   因为活动a10所需时间2。如果V7开始时间比16晚，则V9完成时间就会比18晚，这显然不对。
2. 同理，V8最迟开始时间为14。
3. 对于V5而言，可以从V7、V8两个点开始向前推算，此时要按最小计，即V5(最晚)=min{V7-9,V8-7}=min{16-9,14-7}=7。
   请注意！！，min{V7-9,V8-7}中，V7、V8取的都是前面算出的最迟开始时间（而不是最早开始时间）。

   

   按最小计

   
   按最小计，是因为如果按最大计去计算V5的最晚开始时间，那么加上a7和a8的活动时间后，V7、V8至少有一个会比之前逆推算得出的最晚时间还要晚，这就发生了错误。
4. 同理，可计算出剩下的点

这样，我们可以得到各个状态的最晚时间的表：

最晚时间表

事实上，源点和汇点的最晚时间和最早时间必定是相同的。

3.求出关键路径

求出关键活动，则关键活动所在路径即为关键路径

对于a1：

这表明，a1最早只能从0时刻开始，最晚也只能从（6-6=）0时刻开始，因此，a1是关键活动。

对于a2：

a2最早要从0时刻开始，但是它最晚开始时间却是（6-4=）2。也就是说，从0开始做，4时刻即完成；从2开始做，6时刻恰好完成。从而在[0,2]区间内任意时间开始做a2都能保证按时完成。（请区别顶点的最早最晚和活动的最早最晚时间。图示中的最早最晚是顶点状态的时间，活动的最早最晚开始时间却是基于此来计算的）。
由于a2的开始时间是不定的，所以它不能主导工程的进度，从而它不是关键活动。

一般的，

活动用时X时间，它最早要从E1时刻开始（一开始就开始），最晚要从L2-X时刻开始（即恰好完成）。所以，如果它是关键活动，则必然有E1=L2-X，否则它就不是关键活动。

值得注意的是，顶点的最早开始时间等于最晚开始时间 是 该顶点处于关键路径 的 不充分不必要条件。

上表中蓝色底纹表示的点即为处于关键路径的点。尽管它们的最早时间与最晚时间都相同，但是这与它们是否为关键路径的点无关。因为这还取决于起始点的最早时间以及活动时间。

作者：KyrinWoo
链接：https://www.jianshu.com/p/1857ed4d8128
來源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。