6.7 关 键 路 径
6.7 关 键 路 径
若在带权的有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销（如该活动所需的时间），则称此带权的有向图为用边表示活动的网络，简称AOE网（Activity On Edge network）。
在一个表示工程的AOE网中，应该不存在回路，网中仅存在一个入度为零的顶点（事件），称做开始顶点（源点），它表示了整个工程的开始；网中也仅存在一个出度为零的顶点（事件），称做结束顶点（汇点），它表示整个工程的结束。
例如，图6-35是一个具有15个活动的假想工程的AOE网。图中有11个顶点，它们分别表示事件v1～v11，其中v1表示工程“开始”，v11表示工程“结束”的状态，而边上的权表示完成该活动所需的时间。
图6-35 工程AOE网
在AOE网中，从源点到汇点的所有路径中，具有最大长度的路径称为关键路径。完成整个工程的最短时间就是网中关键路径的长度，也就是网中关键路径上各活动持续时间的总和，关键路径上的活动称为关键活动。
注意：在一个AOE网中，可以有不止一条的关键路径。
下面给出在寻找关键活动时所用到的几个参量的定义。
1．事件的最早发生时间
事件vk的最早发生时间用ee(k)表示，它是从源点v到vk的最长路径长度。事件的最早发生时间决定了所有从vk发出的有向边所代表的活动能够开工的最早时间。可用下面的递推公式计算ee(k)：
ee(1)=0
ee(k)=max{ee(j)+<vj,vk>上的权|<vj,vk>?p(k)}
其中，p(k)表示所有到达vk的有向边的集合。
2．事件的最迟发生时间
事件vk的最迟发生时间用le(k)表示，它是在不推迟整个工程完成（即保证汇点h在ee(n)时刻发生）的前提下，该事件最迟必须发生的时间。le(k)为ee(n)减去顶点vk到顶点结束vn的最长路径的长度。可用下面的递推公式计算le(k)：
le(n)=ee(n)
le(k)=min{le(j)-<vj,vk>上的权|<vj,vk>?s(k)}
其中，s(k)表示所有由vk出发的有向边的集合。
3．活动的最早开始时间
活动ai的最早开始时间用e(i)表示，它是该活动的起点所表示的事件最早发生时间。如果由边<vj,vk>表示活动ai，则有e(i)=ee(j)。
4．活动的最迟开始时间
活动ai的最迟开始时间用l(i)表示，它是该活动的终点所表示的事件最迟发生时间与该活动所需时间之差。如果用边<vj,vk>表示活动ai，则有l(i)=le(k)-ai所需时间。
一个活动ai的最迟开始时间l(i)和其最早开始时间e(i)的差额d(i)=l(i)-e(i)是该活动完成的时间余量。它是在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间。当一个活动的时间余量为零时，说明该活动必须如期完成，否则就会拖延完成整个工程的进度。所以称l(i)-e(i)=0，即l(i)=e(i)的活动ai是关键活动。
求关键路径的过程如下：
（1）求AOV网中所有事件的最早发生时间ee( )。
（2）求AOV网中所有事件的最迟发生时间le( )。
（3）求AOV网中所有活动的最早开始时间e( )。
（4）求AOV网中所有活动的最迟开始时间l( )。
（5）求AOV网中所有活动的d( )。
（6）找出所有d( )为0的活动构成关键路径。
【例6-3】如图6-35所示的AOE网中的关键路径。
解：求所有事件的最早发生时间如下。
ee(1)=0 ee(2)=3
ee(3)=4 ee(4)=ee(2)+2=5
ee(5)=max{ee(2)+1，ee(3)+3}=7 ee(6)=ee(3)+5=9
ee(7)=max{ee(4)+6，ee(5)+8}=15 ee(8)=ee(5)+4=11
ee(9)=max{ee(8)+10，ee(6)+2}=21 ee(10)=max{ee(8)+4，ee(9)+1}=22
ee(11)=max{ee(7)+7，ee(10)+6}=28
求所有事件的最迟发生时间如下。
le(11)=ee(11)=28 le(10)=le(11)-6=22
le(9)=le(10)-2=21 le(8)=min{le(10)-4，le(9)-10)=11
le(7)=le(11)-7=21 le(6)=le(9)-2=19
le(5)=min{le(7)-8，le(8)-4}=7 le(4)=le(7)-6=15
le(3)=min{le(5)-3，le(6)-5)=4 le(2)=min{le(4)-2，le(5)-1}=6
le(1)=min{le(2)-3，le(3)-4}=0
求所有活动的e( )、l( )和d( )如下。
活动a1：e(1)=ee(1)=0， l(1)=le(2)-3=3， d(1)=3
活动a2：e(2)=ee(1)=0， l(2)=le(3)-4=0， d(2)=0
活动a3：e(3)=ee(2)=3， l(3)=le(4)-2=13， d(3)=10
活动a4：e(4)=ee(2)=3， l(4)=le(5)-1=6， d(4)=3
活动a5：e(5)=ee(3)=4， l(5)=le(5)-3=4， d(5)=0
活动a6：e(6)=ee(3)=4， l(6)=le(6)-5=14， d(6)=10
活动a7：e(7)=ee(4)=5， l(7)=le(7)-6=15， d(7)=10
活动a8：e(8)=ee(5)=7， l(8)=le(7)-8=13， d(8)=6
活动a9：e(9)=ee(5)=7， l(9)=le(8)-4=7， d(9)=0
活动a10：e(10)=ee(6)=9， l(10)=le(9)-2=19， d(10)=10
活动a11：e(11)=ee(7)=15， l(11)=le(11)-7=21， d(11)=6
活动a12：e(12)=ee(8)=11， l(12)=le(10)-4=18， d(12)=7
活动a13：e(13)=ee(8)=11， l(13)=le(9)-10=11， d(13)=0
活动a14：e(14)=ee(9)=21， l(14)=le(10)-1=21， d(14)=0
活动a15：e(15)=ee(10)=22， l(15)=le(11)-6=22， d(15)=0
从以上计算得出，图6-35中AOV网的关键活动为a2，a5，a9，a13，a14和a15。这些活动构成了关键路径。
