7.7　关键路径

拓扑排序可以判断一项工程能否顺利进行,那么整个工程完成的最短时间是多少？哪些子工程的延迟将影响整个工程进度,而加速这些子工程能否提高整个工程的效率呢？为了解决这些问题,引入了AOE网（activity on edge network）概念。

AOE网（activity on edge network）是一个有向网。其中,用边表示活动（子工程）；用边的权值表示活动的持续时间；用边两端的顶点分别表示工程中的瞬间行为或事件,即活动的开始和结束。在AOE网中有两个特殊的顶点:一个是入度为0的顶点为源点,代表整个工程的开始点；另一个即出度为0的顶点为汇点,代表整个工程的结束点。图7－38所示是一个有11项活动,9个事件的AOE网。

图7－38　AOE网

AOE网的主要性质如下。

（1）只有在某个顶点所代表的事件发生后,从该顶点出发的各有向边代表的活动才能开始。例如,图7－38中顶点5事件发生后,活动a₇和a₈才能开始。

（2）只有某一顶点的所有入边代表的活动已经结束,该顶点所代表的事件才能发生。如图7－38中活动a₄和a₅活动结束后,事件5才能开始。

在AOE网中,有些活动可以并行地运行,因此,完成整个工程所需要的最少时间不是所有活动所需时间的累加,而是从源点到汇点之间的最长的一条路径,这条最长的路径被称为关键路径（critical　path）。

在AOE网中,有些活动可以并行地进行,如图中的a₁和a₂。因此,从源点到各个顶点,以至从源点到汇点的有向路径可能不止一条,而且这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同,但只有各条路径上所有活动都完成了,整个工程才算完成。因此,完成整个工程所需的时间取决于从源点到汇点的最长路径长度,即关键路径（critical path）的长度。一个AOE网的关键路径可能不只一条。关键路径上的活动称为关键活动,其完成时间会影响整个工程的完成时间。

为了求解AOE网的关键路径和关键活动,下面引入几个概念。

（1）事件的最早发生时间ve（i）:只有顶点事件所有入边活动都完成后,顶点事件才能发生,因此,从源点到任意顶点v_i的最长路径长度称为事件v_i的最早发生时间。源点对应事件的最早发生时间为0。

（2）活动的最早开始时间ee（i）:只有顶点对应的某个事件发生后,从该顶点出发的有向边对应的活动才能开始。设活动a_i在边〈v_j,v_k〉上,则a_i的最早开始时间为v_j的最早发生时间。

（3）事件的最迟发生时间vl（i）:保证汇点v_n在ve（n）时刻完成的前提下,事件v_i允许的最迟开始时间。在不推迟工期的情况下,一个事件最迟发生时间应该等于汇点的最早发生时间减去从v_i到v_n的最大路径长度。

（4）活动的最迟开始时间el（i）:在不会引起工期延误的前提下,活动a_i允许的最迟开始时间。因为事件发生表明以事件顶点为终点的入边所表示的所有活动均已完成,所以事件的最迟发生时间也是所有以事件顶点为终点的入边所表示的活动的最迟完成时间。为了不推迟工期,活动a_i的最迟开始时间el（i）应该是a_i的最迟完成时间减去a_i的持续时间。

（5）时间余量:活动的最早开始时间和最迟开始时间的差额称为时间余量。没有时间余量的活动即为关键活动。关键活动的推延将直接导致整个工程的推延,而提前完成非关键活动并不能加快整个工程的进度。

由上述概念定义可知,为了找出关键活动,需要求出各个活动的最早开始时间和最晚开始时间,以判别一个活动是否满足时间余量为零。求各个活动的最早开始时间和最晚开始时间需要求事件的最早发生时间和最晚发生时间。由此可以得到求关键路径的算法如下。

（1）对AOE网进行拓扑排序,记录排序结果。如果得到的拓扑有序序列中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径,此时算法终止；否则执行步骤（2）。

（2）从源点v₁出发,令ve（1）＝0,按拓扑序列依次求出其余各顶点的最早发生时间。

ve（j）＝max{ve（i）＋dut（i,j）}　（i,j）∈E,2≤j≤n

（3）从汇点v_n出发,令vl（n）＝ve（n）,按拓扑逆序求出其余各顶点的最迟发生时间。

vl（i）＝min{vl（j）－dut（i,j）}　（i,j）∈E,1≤i≤n－1

（4）根据各顶点的ve和vl值,求每条边代表活动的最早开始时间ee（i）和最迟开始时间el（i）。设活动a_i由弧（j,k）表示,其持续时间记为dut（j,k）,事件的最早开始时间为ve（j）,最迟开始时间为vl（j）,则有如下关系。

ee（i）＝ve（j）

el（i）＝vl（k）－dut（j,k）

（5）若某条边满足条件ee（i）＝el（i）,则该边对应的活动为关键活动。

图7－39所示为求解图中AOE网的关键路径和关键活动的过程。

图7－39　关键路径求解过程

本章小结

1.图的基本概念:顶点、边、度、完全图、子图、路径、路径长度、连通图、权、网等。

2.图的邻接矩阵、邻接表、邻接多重表三种存储结构的实现。

3.图的深度优先和广度优先搜索遍历的过程、算法描述及相应的时间复杂度。

4.根据普里姆算法和克鲁斯卡尔算法求图的最小生成树的过程、算法描述及相应的时间复杂度。

5.图的拓扑序列和拓扑排序的概念,求图的拓扑序列的方法、算法描述及相应的时间复杂度。

6.用Dijkstra算法求图中单源最短路径的过程、算法描述及相应的时间复杂度。用弗洛伊德（Floyd）算法求图中所有顶点对间的最短路径的过程、算法描述以及相应的时间复杂度。

7.求AOE网的关键活动和关键路径的过程和算法描述。