关键路径VS最短路径

关键路径算法一般会在最短路径算法的后面进行讲解。

这就需要我们首先区分出关键路径算法和最短路径算法在前提上的不同：

• 最短路径算法是找尽可能短的路来保证路径长度最小，你只需要找出一条最短的路就行。

• 但是在关键路径里，一个顶点是有多个前提的，只有前提的路径都走完，才能发生该顶点的事件，那么只有最长的路径走完，保证其余短的路都早已经走完，该事件才发生。

事件和活动

在关键路径算法中，我们将事件定义为AOE图中的“顶点”，将活动定义为AOE图中的“弧”。

事件的发生和开始

这里要首先弄明白的是两个词，也就是后面要学到的概念中的 "发生" 和 "开始"。

• “发生”是针对于事件的，也就是图中的顶点。什么叫事件发生了呢？只有在指向该顶点的所有有向边对应的活动结束，该顶点所代表的事件才发生。举个例子，一个事件C，它仅被两条边a, b指向，仅当a，b两活动都完成时，事件C发生。

• “开始”是针对于活动的，也就是图中的弧。只有在一个顶点所代表的事件发生后，从该顶点出发的所有边对应的活动才能开始。什么时候开始？即可以在事件一完成就立马开始接下来的活动，也可以推迟活动开始的时间。

事件的最早发生时间（etv）

我们前面说过，发生是针对于事件的，一个事件要发生，首先要指向它的活动都完成。

一个事件C，被两个活动a，b指向，a活动的耗费时间是3， b活动的耗费时间是5。

那么看下图，从开始到C事件的发生要多久呢？

是最大路径长度5，因为C事件发生的前提必须是a，b两活动完成（活动可同时进行）。

C事件只有等到b完成才发生，最早完成时间由耗时最久的路决定，所以这就是为什么要取最长路径长度。

因此：事件的最早发生时间推导公式：

事件的最晚发生时间（ltv）

最晚发生时间的意义是：在不推迟整个工程完成的前提下，该事件最晚的发生时间。

因此我们可以想象：

• 在一个AOE图中的汇点，其最晚发生时间和最早发生时间一定是相同的，因为汇点事件的发生事件一定会直接决定整个工程的完成时间。

• 而一个非汇点代表的事件，其实就是我们可以将其理解为一个和其他事件并联的事件，那么如果这个事件所在的路径所需的事件比与其并联的其他路径短，则负责这个事件的人就可以偷懒了，比如这条路径需要花费的时间比别的路径少1小时，那么负责这条路径的人就可以晚开工1小时，并且和其他路径同时完成（到达汇点）。这就是最晚发生时间。

• 因此对于一个非汇点，其最晚发生时间是由其后面的后继顶点反推得到的。

仍然使用上面的例子：

在这个例子中，C为汇点，其最晚发生时间等于最早发生时间，都是5。

而与其相关联的两个顶点A、B中，A节点的路径权值较小，因此我们可以知道，A路径可以偷懒。

很容易可以计算出，A事件的最晚发生事件为2，B事件的最晚发生事件为0（不能偷懒）。

后面我们还需要举一个复杂一些的例子，来解释这个事件最晚发生事件的推导公式是怎么产生的：

（红色笔标注了事件的最早发生时间，绿色笔标注了事件的最晚发生时间）

这里我们可以看到，和上图不同，C顶点有2个出度，也就意味着它影响着两个后继顶点。

如果我们仍用上次的方法，用110-10得100，可以认为C事件最晚在第100天发生吗？

仔细看看是不对的，B顶点的发生前提是C顶点要发生，如果C在第100天才发生，那么B事件等不了啊，B最迟在第10天就要发生。

正确的做法应该是B事件的最迟发生时间减4天得第6天。

由此可见，一个顶点的最晚发生时间其实是由它的后继节点所决定的，这也就解答了为什么我们要从汇点开始倒着往起点推。

因此我们也可以理解为什么公式中使用的是 Min{} 取最小。

就比如刚刚的例子，C有两个选择——第6天或者第100天，必须得选最小的以保证你不会耽误任何后继节点的最晚发生。

因此：事件的最早发生时间推导公式：

活动最早开始时间（ete）

前面提到过，“开始”是针对活动，也就是图中的弧的概念。

活动的最早开始时间，理解起来非常容易，弧的起点所依附的事件一旦发生就立刻开始，就是最早开始时间了。

公式：若边<k, j> 表示活动i，则有ete(i) = etv(k)

活动最晚开始时间（lte）

最晚开始时间要和该边指向事件的最迟发生时间挂钩。

也就是边所指向的事件最晚发生时间 - 边对应的活动所需时间。

公式: 若边<k, j> 表示活动i，则有lte(i) = ltv(j) - Weight(k,j)

时间余量（d）

d(i) = lte(i) - ete(i)

即活动最迟开始时间与最早开始时间的差额，这代表着活动可以拖延的时间。

如果一个活动的时间余量为0，就意味着该活动不能拖延时间，称为关键活动，必须立即完成。

而时间余量为0的所有边连起来，就是关键路径了。

求解顺序：

• 要求时间余量d，就要先求活动的最早开始时间ete和最迟开始时间lte，

• 要求ete和lte就要先求事件最早发生时间etv和最晚发生时间ltv

注意事项

• 关键路径上的所有活动都是关键活动， 它是决定整个工程的关键因素，因此可以通过加快关键活动来缩短整个工期。但是也不能任意缩短，因为一旦缩短到一定的程度，该关键活动就可能变成非关键活动了

• 网中的关键路径不唯一，对于有好几条关键路径的网，只加快其中某一条关键路径上的活动并不能缩短工期。只有加快存在于所有关键路径上的关键活动才能达到缩短工期的目的。

主要参考：

• https://zhuanlan.zhihu.com/p/170603727

• 王道考研