关键路径求解

前置知识

AOV网与AOE网

AOV网全称(Activity On Vertex),AOE网全称(Activity On Edge)
AOV网和AOE网都是有向无环图，他们的区别在于
AOE网的边是有权重的，因为”Activity On Edge”用边来表示活动
如果边上什么信息也没有，怎么表示活动？

正文

多数的关键路径讲解文章使用这些表示方法:
打个比方，我们现在有一个工程，就是将大象装进冰箱，那么源点就相当于我们现在接到这样一个任务，而汇点则表示我们完成了这个任务。那么我们之前所讲的打开冰箱门，将大象装进去，关上冰箱门就属于活动本身（即所表示的信息），打开冰箱门所需要的时间就是活动所需要的时间，而完成某一个活动所到达的顶点就表示一个事件（冰箱门打开）。下图中的红色顶点表示源点，表示汇点。

ETV (Earliest Time Of Vertex)：事件最早发生时间，就是顶点的最早发生时间
LTV (Latest Time Of Vertex)：事件最晚发生时间，就是每个顶点对应的事件最晚需要开始的时间，如果超出此时间将会延误整个工期
ETE(Earliest Time Of Edge)：活动的最早开工时间，就是弧的最早发生时间 （活动的最早开工时间其实就是事件最早发生时间）
LTE(Lastest Time of Edge)：活动的最晚发生时间，就是不推迟工期的最晚开工时间

但我想给ETV换个命名：

改 ETV 为 LongestTimeToVertex 到顶点的最长路径时间

即图中An，也就是弧的权重

第一步：利用公式 = MAX {}
遍历LongestTimeToVertex数组找到每个顶点到源点的最大时间

第二步：LTV[9] = LongestDistanceToVertex[9]
why???

最后一步的最晚完成时间当然是卡着deadline啦 (∠・ω< )⌒★
然后利用公式 = MIN{}
往回遍历LTV数组找到每个顶点的最晚开始时间

第三步：判断ETE[i] 与 LTE[i] 是否相等，相等时对应的弧就是关键路径上的弧
why???
最早开始时间等于最晚开始时间说明不存在摸鱼时间
不存在摸鱼时间的路径就是关键路径↓

以下引自CSDN博主「壮壮不太胖^QwQ」的原创文章

关键路径的讨论

1.若网中有几条关键路径，则需要加快同时在几条关键路径上的活动。
如：a11、a10、a8、a7。
2.如果一个活动处于所有的关键路径上，那么提高这个活动的速度，就能缩短整个工程的完成时间。
如：a1、a4。
3.处于所有关键路径上的活动完成时间不能缩短太多，否则会是的原来的关键路径变成非关键路径。这时，必须重新寻找关键路径。
如：a1 由 6天变成 3天，就会改变关键路径。

文中引用:
①图解：什么是关键路径？-CSDN博客 作者：壮壮不太胖^QwQ
②10分钟了解关键路径及如何求得关键路径-CSDN博客 作者：ChatAlgorithm