AOE网络关键路径求解的通俗理解

AOE网络是一种以边主导的活动网络，简单来说是一种有向加权图，通常有一个起点（源点）和一个终点（汇点），中间顶点表示某个事件，或叫里程碑，而有向边叫做活动，AOE网络通常可以用来表达某些带有前驱后继关系的一系列活动。关键路径是指影响最终活动进程的所有活动构成的路径，求解AOE网络的关键路径，可以使活动时间安排更合理，也更容易找出网络中的瓶颈并加以改进。

1.从番茄炒蛋出发

番茄炒蛋想必很多人都做过，虽然过程可能有点差异，但是主流做法基本一致，下面以一顿饭为例，来说明AOE关键路径的计算。请看下图

请忽略其中不大合乎现实的点哈，比如煮饭只需要8分钟。。。

所谓关键路径，就是从源点到汇点，某个路径上的活动，直接决定了最早的开饭时间。AOE网络图看起来不太直观，下面将它转化成时序图

从这张图中，我们可以很直观的看出来关键路径，如果加盐出锅可以快1分钟，我们就可以早1分钟吃饭，但煮饭时间再缩短1分钟，对提前吃饭是没有帮助的。继续分析下去，我们发现【番茄去皮->番茄切块->炒鸡蛋->鸡蛋下锅->加盐出锅】是整个活动网络的关键路径。那既然这么直观就能看出来，为什么还要求解呢？

因为这是为了讲解AOE网络而构造的简单有向图，实际应用中的网络可能更复杂，很难直观看出结果。此外，有时网络活动的耗时是动态变化的，例如把上图中的事件想像成异步管道（例如kafka），把活动想像成发布或订阅数据的处理程序，处理程序的耗时可能随着代码的改进而变化，这就需要通过关键路径算法来找出瓶颈活动并加以改进。

1.1.松弛时间与关键路径

示例中不难发现，有些事件或活动，是有灵活调整的空间的。比如鸡蛋打散，即使晚个2分钟进行，也不影响后面炒鸡蛋的开始时间，这种非关键路径上的活动或事件可以调整的现象，叫做松弛。关键路径的主要特征就是，其路径上的活动或事件不允许松弛，因为一旦移动关键活动或事件，就会影响开饭的时间（干饭人不允许这种情况发生！）

可以得出一个结论，可松弛的活动具有这样的特点，它的最早开始时间和最晚开始时间是可以不相等的。而关键路径活动，这两个时间一定是相等的。所以找出关键路径的问题就变成了找到所有活动的最早可以开始时间和最迟可以开始的时间。因为活动的权重是固定的，所以可以不用关注活动的最早/最迟结束时间。

2.事件的开始时间

在有向图中活动即是有向边，而事件就是表达有向边的顶点，所以活动的开始时间，与事件的开始时间紧密相关。先来看下事件的开始时间。
事件有两种开始时间，一种是最早开始时间，用$Ee$表达，一种是最迟开始时间，用$El$表达。

2.1.最早开始时间$Ee$

事件A要开始的前提是，它之前的活动都完成，跟A事件之后或不经过A的其他活动无关，比如A4备菜完毕这个事件，取决于前面最长的番茄处理过程，即5+2=7min

用公式来表达就是：
$$Ee[A]=max(Ee[A_{pre}]+W<A_{pre},A>)$$
$Ee[A_{pre}]$是A事件的所有前驱事件顶点，$W<A_{pre},A>$是A的前驱事件到A的活动权重。

计算方式是，从源点出发进行BFS，每次遇到顶点A，都将A的到达时间更新为更大的值，一直计算到汇点。最终计算最早开饭时间为13min。

2.2.最迟开始时间$El$

因为我们希望不要延迟开饭的时间，所以El的含义是，为了保障开饭这个事件的$Ee[A9]$时间前提下，A不能晚于什么时间开始。还是以A4为例，要保证最早的开饭时间$Ee[A9]$，A6就不能晚于11min，A5不能晚于10min，A4不能晚于7min。为什么不是8分钟呢？因为A4-A5-A6这条路径要比A4-A6更长，所以A4-A5-A6这条线是影响开饭时间的关键活动。

因此，影响El的是事件A到汇点中最长的路径，用公式来表达如下：
$$El[A]=min(El[A_{next}]-W<A,A_{next}>)$$
这个计算也很简单，只需要设$El[汇点]=Ee[汇点]$，并从汇点开始沿有向边的逆向进行BFS，计算遇到顶点的El即可。

3.活动的开始时间

掌握了所有事件的$Ee$和$El$，我们来看活动的最早开始时间$e$和最迟开始时间$l$。

3.1.活动的最早开始时间

值得庆幸的是，活动的最早开始时间就是其出发顶点的最早开始时间，这很符合直觉。所以这里不需要计算，只需要令$e[<A,A_{next}>]=Ee[A]$即可，其中$<A,A_{next}>$是从A出发的活动。

3.2.活动的最迟开始时间

重头戏来了，这个是比较不容易理解的地方。因为活动$<A,A_{next}>$的最迟开始时间，并不等于事件A的最迟开始时间$El[A]$，思考一下这是为什么？

one Mississippi…
two Mississippi…
…

OK…因为事件A的最迟开始时间，是基于A到开饭的最长路径长度计算得来的。从A出发的活动可能有多个，$<A,A_{next}>$未必是这条最长路径上的活动。比如炒番茄这项活动，我们完全可以等炒鸡蛋活动开始1分钟后再开始炒番茄，也不会影响最后的开饭。而炒鸡蛋和炒番茄，都是从A4出发的活动。

所以影响炒番茄活动的，是它的到达顶点$A6$的最迟允许开始时间。其计算方式如下：
$$l[<A,A_{next}>]=El[A_{next}]-W<A,A_{next}>$$
属于是从活动的终点推导活动的最迟开始时间了，所以从时序图上也能看出，炒番茄这项活动的最早开始时间是7min，最迟开始时间是8min，显然它不是关键路径。

4.求解关键路径

目前我们掌握了$e$和$l$，即所有活动的最早和最迟开始时间，如果上面所述都理解了，那最后的关键路径求解就不用说了吧（不理解的话再仔细看下1.1部分）

重复一下结论，这里的关键路径是【番茄去皮->番茄切块->炒鸡蛋->鸡蛋下锅->加盐出锅】

干饭人开饭！(╹▽╹)