关键路径核心算法：求一条不影响整体工程进度的最优路径方案，下面我将分为三个步骤详细讲解该算法。
第一步：求各个事件（结点）的最早时间（在这里我们用一个数组va[]来存储各个事件的最早时间）和最晚时间（在这里我们用一个数组vb[]来存储各个事件的最迟时间），该工程图如下所示。
首先进行拓扑排序（0，1,2,3）求最早时间，得到：
va[0]=0;
va[1]=3;
va[2]=max{va[0]+a2,va[1]+a3}=7;
va[3]=max{va[0]+a0,va[1]+a4,va[2]+a5}=12;
然后逆拓扑排列（3,2,1,0）求最迟时间，得到
vb[3]=12;
vb[2]=7;
vb[1]=min{vb[2]-a3,vb[3]-a4}=3;
vb[0]=min{vb[3]-a0,vb[2]-a2,vb[1]-a1}=0;
接下来求该图“边”的最早时间用w(ai)表示，“边”的最迟时间用l(ai)表示；（注意，上面的是结点对应的的最早时间和最短时间，不要混淆）
最早事件时间，过程如下
w(a1)=w(a2)=w(a0)=va[0]=0；
w(a3)=w(a4)=va[1]=3;
w(a5)=va[2]=7;
最迟发生时间，过程如下
l(a0)=vb[3]-a0=7;
l(a1)=vb[1]-a1=0;
l(a2)=vb[2]-a2=5;
l(a3)=vb[2]-a3=3;
l(a4)=vb[3]-a4=11;
l(a5)=vb[3]-a5=7;
最后一步，建一个图表，将边的最早发生时间和边的最晚发生时间对比，如果一样，则这条边就是关键路径上的一条子路径。
| 空 | 最早发生时间 | 最迟发生时间 | 相同点 |
|---|
| a0 | 0 | 7 | × |
| a1 | 0 | 0 | √ |
| a2 | 0 | 5 | × |
| a3 | 3 | 3 | √ |
| a4 | 3 | 11 | × |
| a5 | 7 | 7 | √ |
将相同的提取出来得到关键路径（a1,a3,a5）;
即a1->a3->a5就是这个图的关键路径。
版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/weixin_42373888/article/details/81605563
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。
-
发表于 2023-01-03 21:22:19
- 阅读 ( 410 )
- 分类：算法
