关键路径这个知识点在软件设计师考试中，是一个难点。

　　说到关键路径这个概念，大家应该多少有些印象，可能都知道它是“最长路径”而不是“最短路径”，但说到它为什么是最长路径，提出这个概念的用意何在，它有什么应用，在计算机中关键路径是如何求的等问题却没有几个人能真正搞清楚，甚至书上给出了完整的例子，都有很多人看不懂。下面我先会简单的说明基本概念，然后以一个例子，结合平时学员的疑问，对这个知识点进行详细的分析。

　　在AOV网络中，如果边上的权表示完成该活动所需的时间，则称这样的AOV为AOE网络。例如，图1表示一个具有10个活动的某个工程的AOE网络。图中有7个顶点，分别表示事件1～7，其中1表示工程开始状态，7表示工程结束状态，边上的权表示完成该活动所需的时间。

　　下面我们来理解一下关键路径的思想，图1虽节点不多，但是为了让问题变得更为简单、直观，我们画另一个AOE网络，如图2所示。

　　从图2中我们可以看出，关键路路径实际上是从源点到目的地的最长路径。为什么是最长路径呢?因为图中的某些事件是可以并发执行的。如图2所示，当到达V1后，可以同时往V2，V3，V4三个方向走，而V2，V3，V4都有到Vk的路径，且长度都为1，并且Vk是终点，则关键路径是V1->V2->Vk。因为这条路径最长，只要这条路径到目的地Vk时其他的都已经到达Vk。而在这条关键路径上的活动a2，a5称为关键活动。

　　为了找出给定的AOE网络的关键活动，从而找出关键路径，先定义几个重要的量：

　　Ve(j)、Vl(j) ：顶点j事件最早、最迟发生时间。

　　e(i)、l(i)：活动i最早、最迟开始时间。

　　从源点V1到某顶点Vj的最长路径长度称为事件Vj的最早发生时间，记为Ve(j)。Ve(j)也是以Vj为起点的出边所表示的活动ai的最早开始时间e(i)。

　　在不推迟整个工程完成的前提下，一个事件Vj允许的最迟发生时间记为Vl(j)。显然，l(i) =Vl( j)-(ai所需时间)，其中j为ai活动的终点。满足条件l(i) =e(i)的活动为关键活动。

　　求顶点Vj的Ve(j)和Vl(j)可按以下两步来做。

　　(1)由源点开始向汇点递推。

　　其中，E1是网络中以Vj为终点的入边集合。

　　(2)由汇点开始向源点递推。

　　其中，E2是网络中以Vj为起点的出边集合。