CHARLIE SAYS

关键路径在项目管理计算工期等方面有广泛的应用，提升工期就是缩减所有关键路径上的工期，并且在实现时需要应用到之前拓扑排序的算法（前提：有向无环图，有依赖关系）。

关键路径相关名词

相关术语：

• AOV 网络（Activity On Vertex Network）：有向图，用顶点表示活动，用弧表示活动的先后顺序。
• AOE 网络（Activity On Edge）：有向图，用顶点表示事件，用弧表示活动，用权值表示活动消耗时间（带权的有向无环图）。
• 活动：业务逻辑中的行为，用边表示。
• 事件：活动的结果或者触发条件。
• 关键路径：具有最大路径长度（权重）的路径，可能不止一条。
• 活动的两个属性：e(i) 最早开始时间，l(i) 最晚开始时间。
• 事件的两个属性：ve(j) 最早开始时间，vl(j) 最晚开始时间。

AOV 和 AOE 的对比：虽然都是用来对工程建模，但是还是有很大不同，主要体现在：

• AOV 网是顶点表示活动的网，它只描述活动之间的制约关系；
• AOE 网是用边表示活动的网，边上的权值表示活动持续的时间。

一个 AOE 网的结构示意（顶点为事件，边为活动，权值为活动耗时；原文图片丢失，据文字重绘）：

graph LR
    V1((v1)) -- "a1 = 3" --> V2((v2))
    V1 -- "a2 = 2" --> V3((v3))
    V2 -- "a3 = 4" --> V4((v4))
    V3 -- "a4 = 5" --> V4
    V4 -- "a5 = 6" --> V5((v5))

关键路径的实现

4 个关键概念

• 事件最早发生时间：事件最早发生时间 etv（earliest time of vertex），即顶点 Vk 的最早发生时间。
• 事件最晚发生时间：事件最晚发生时间 ltv（latest time of vertex），即顶点 Vk 的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期。
• 活动的最早开工时间：活动的最早开工时间 ete（earliest time of edge），即弧 ak 的最早发生时间。
• 活动的最晚开工时间：活动的最晚开工时间 lte（latest time of edge），即弧的最晚发生时间，也就是不推迟工期的最晚开工时间。

4 个时间的关系

我们可以由事件的最早发生时间和事件的最晚发生时间求出活动的最早和最晚开工时间：由 etv、ltv 可以求得 ete、lte，然后再根据 ete[k] 是否与 lte[k] 相等来判断 ak 是否是关键活动。

算法实现

推演图（原文图片丢失）的推导方向如下：

• etv 从左向右推导；
• ltv 从右向左推导；
• ete：活动最早开工时间需要和 etv 事件最早发生时间结合；
• lte：活动最晚开工时间需要和 ltv 事件最晚发生时间结合（都是倒序获得）。

推演的具体步骤可以参考关键路径算法的实现与推演。

参考文章

• https://blog.csdn.net/qq_25508039/article/details/75390192
• https://www.cnblogs.com/ssyfj/p/9496969.html
• https://www.cnblogs.com/Braveliu/p/3461649.html
• https://www.cnblogs.com/lisen10/p/10876110.html

系列导航

• 上一篇：图：最短路径 Dijkstra & Floyd
• 下一篇：算法思想知识体系详解
• 相关篇：图：拓扑排序（关键路径实现的前提是有向无环图与依赖关系，需借助拓扑排序）