数据结构—快速掌握如何手动求解关键路径

看到一道题，分析如何手动求解关键路径，文末有题目出处。如上图，红点表示状态，边表示活动及其所需要的时间。这是用箭线表示活动、节点表示事件的一种网络图绘制方法，也称为双代号网络图（AOA）。

下面我们将利用其它快捷方法求出关键路径。

方法一：逆推法

从最末端的活动开始：
step1：将最末端的活动时间标记为0（这里选汇点，将汇点当做一个虚活动），活动a10与0相加，标注在它的前置活动a7上方，同理，活动a11与0相加，标注在它的前置活动上方（这里a11有两个前置活动，都要标注）：
依次选最大往前加，标注在前一个活动上方:step2. 活动a7与标注它上方的a10相加，标注它前一个活动上方，由于a7是直接后继活动，所以它的前导活动a4上方标记a7，这里a4也是a8的前导活动，我们要选关键路径，就是要选最大，但是这里有个尴尬的地方，a7和a8算下来都是11，a8和a9同理：

step3. 继续往前推，活动a4的前导活动是活动a1，有个要注意的地方，活动a4上方的活动有多个，这里我们要选活动时间最大的和a4相加，然后标记到活动a1上方，活动a5和a6同理，分别标注到它们的前导活动a2和a4的上方：

step4. 将源点也当做一个虚活动，将a1，a2，a3计算后的结果标注在源点上方，继续选最大，得出关键路径长度 18：

最后，从左往右看 a1， a1上方标注的a4，然后到a4，a4上方标注的a7和a8，说明关键路径有两条，继续往后推一直到汇点。所以关键路径为：
a1 --> a4 --> a7 --> a10
a1 --> a4 --> a8 --> a11

方法二：单代号网络图（七格图）

单代号网络图（七格图） ，是用于编制项目进度网络图的一种方法，活动节点表示法，单代号网络图（AON：Activity-On-Node）

七格图画法

转为单代号网络图， 画出七格图-顺推，得出工期

绘制活动，从左至右依次算出EF，最终得出工期=18
相关公式（ES从第0天开始）
最早开始及最早完成（顺推）：
最早开始ES = 取最大值（前置活动的最早完成EF）；
最早完成EF = 最早开始ES + 持续时间DU

最早开始时间，顺推选最大（因为只有前置活动全部完成才能开始下一个活动）;

逆推，得出活动最晚开始时间和总浮动时间

从右至左，从最后一个活动完成：最早的完成时间 = 最晚完成时间 = 工期
依次算出 LS 和 TF，最终得出关键路径， 长度 18

相关公式（最后一个活动的LF = 最后一个活动的EF = 工期 = 18）
最晚完成LF = 取最小值（后续活动的LS）
最晚开始LS = 最晚完成LF - 持续时间DU

最晚完成时间，逆推选最小（同理，因为只有前置活动全部完成才能开始下一个活动）;

根据活动的总浮动时间，得出关键路径

总浮动时间（总时差TF）= 最迟开始LS - 最早开始ES
或
总浮动时间（总时差TF）= 最迟完成LF - 最迟开始EF
或
总浮动时间（总时差TF）= 关键路径时长 - 非关键路径时长

☆☆☆关键路径上总浮动时间为0

由上图，关键路径共有两条：
a1 --> a4 --> a7 --> a10
a1 --> a4 --> a8 --> a11

我
是
一
条
严
肃
的
分
割
线

至此，开篇的问题已经解决了，可能有人会有异议，这个方法还是很复杂啊，看着还挺麻烦。但如果面对一个更复杂的活动图，那么七格图的优势就很明显了，如果有兴趣，可以继续往下看：

这是一个相对比较复杂的活动图，很容易让人感到凌乱，如果将它绘制成单代号网络图（看着很密集很恐怖的样子，但其实跟原图差不多）：

很容易得出工期=23，继续从后往前推，得到关键路径（红色标记）：

关键路径为：1-2-4-5-7-8-10
同理，也可用逆推法进行手动求解：

题目出处：https://www.jianshu.com/p/1857ed4d8128
单代号网络图（七格图）：https://jingyan.baidu.com/article/456c463b24da7c0a5831448a.html

感谢您的仔细阅读，欢迎点赞收藏加关注！