一，关键路径问题的相关概念

通常，一个项目可以被拆分成多个子项目，多个子项目间会具有并行和串行的特点。

例如造汽车时，造发动机和造车轮是两个可以并行完成的任务，而组装整车又必须等发动机和车轮等部件完成后才能开始，具有串行的特点。

• 关键路径是指能影响项目整体时间的活动和事件的集合，是项目中最长的路径。
• 关键路径问题也即指从多个子项目中流程中找到影响项目整体运营时间的关键路径。

对以上问题进行建模可以得到如下常用例子：

• 活动结点（V1~V9），表示整个项目的阶段性结点，比如V2就是活动W1的结束结点，也是W4的开始结点，类似于图一中的组装发动机结束，组装完成等；
• 活动持续时间（W1~W11），表示整个项目的子项目活动，其值表示该活动的持续时间。

我们先事后诸葛亮一把，可以知道其中W1>W4>W7>W10是关键路径，我们把除以上四个活动其他活动的时间缩短，并不能缩短整个项目的时长，只有减少关键路径上的活动持续时间才能减少整个项目的时间。也即，减少造轮子的时长对整个造车项目时长无影响，但缩短造发动机时长就能立即减少整个造车时长。

那怎么才能找到这样一条关键路径呢？这里我们需要引入一些概念：

AOE网（Activity On Edge Network）指一个带权值有向图中，结点表示活动结点，边表示活动，权值表示活动持续时间。AOE网具有特性：

• 只有所有引入边表示的活动都完成后，该活动结点才达成。 比如使V5达成，必须要W4和W5代表的活动完成，如果一个没完成就需要等待其完成（这里有逻辑关系“and”的特点）。
• 只有在活动结点达成后，从该结点出发的活动才能开始。 比如V5达成后，W7和W8事件才能开始。

另外，还有四个要用到的时间点定义：

• 结点最早达成时间VE(Vertex Early)：能达成该结点的最早时间，这就需要所以到该结点的活动都执行完（并不是最早到达该结点的时间，这点容易搞混，是必须所有活动到达的and关系，不是某个到达的or关系）；
• 结点最晚达成时间VL(Vertex Late)：为了在规定时间内使下一个结点达成，当前结点的最晚达成的时间，也可以称为下一任务的最晚开始时间。

对以上两个概念进行举例解释，你有9个小时完成你的作业，你的作业完成需要2个小时，只要在9个小时内抽出2个时间完成作业即可，极端的选择有两种：
其中V1表示开始写作业结点，V2表示写完作业结点。

如果选择立马开始写作业，也即左图，则结点V2最早达成时间VE(2) = 2，也即写完作业结点最早达成在2时；

如果选择最后再写作业，也即右图，则结点V1最晚达成时间VL(1) = 7，也即开始写作业结点最晚达成要在7时;

• 活动最早开始时间AE(Activity Early)，指对应与边的活动的最早开始时间，区别于结点。
• 活动最晚开始时间AL(Activity Late)，指对应边的活动的最晚开始时间，区别于结点。

有人说，这和上面讲的结点的两个时间一样啊，其实在单边对单点时时一样的，但如果出现对边对单点，单点对多边时，取值会不相同。以上四个定义的概念之间的准确关系为：

• VE(j) = max{VE(i) + W(i,j)}，i可以取多个值，迭代过程从原点到终点；i左j右；
• VL(i) = min{VL(j) – W(i,j)}，j可以取多个值，迭代过程从终点到原点；i左j右；
• AE(当前活动) = VE(当前活动的起始结点)；通过结点时间求活动边时间；
• AL(当前活动) = VL(当前活动的结束结点) – W(当前活动)；通过结点时间求活动边时间；

二，关键路径求解算法

• 步骤1：求解所有结点的VE和VL；
• 步骤2：根据VE和VL求解所有边的AE和AL；
• 步骤3：找到AE和AL相同的边，连接起来及为关键路径。

以下图为例，完成上述步骤：

另一种解释：

我们应该见过一种游戏，我们关注这种游戏的不同长度的方块之间的位置关系，比如卒可以在黄忠旁边上下移动。

这里我们把每个活动的持续时间作为方框的长度，根据活动之间的先后关系放置方框，可以将AOE网改成如下图所示：
其中V5有两个活动输入，则V5的位置在W4和W5之后，因为W4更长因而选择V5接在W4活动之后，同理V8和V9也是如此。我们也可以理解V5,V8,V9为一种“多路对齐器”。

首先，整个项目的所有活动W1~W11都往左靠，也即尽量赶早运行，满足“多路对齐器”，得到最早V9在18时完成项目。

再以18时为结束时间，整体活动W1~W11往右靠，也即都赶晚运行，但也必须满足V5,V8,V9处的“多路对齐器”。

可以发现活动W1，W4，W7，W10无论赶早赶晚，其路径上的结点时间都不变，这就是关键路径！