一 点睛

AOV 网可以反映活动之间的先后制约关系，但在实际工程中，有时活动不仅有先后顺序，还有持续时间，必须经过多长时间该活动才可以完成。这时需要另外一种网络——AOE网，即以边表示活动的网。AOE 网是一个带权的有向无环图，节点表示事件，弧表示活动，弧上的权值表示活动持续的时间。

例如，有一个包含 6 个时间、8个活动的工程，如下图所示。V0 和 V5 分别代表工程的开始和结束，在活动 a0、a2 结束后，时间 V1 才可以开始，在 V1 结束后，活动 a3、a4 才可以开始。

在实际工程应用中通常需要解决两个问题。

1 估计完成整个工程至少需要多少时间。

2 判断哪些活动是关键活动，即如果该活动被耽搁，则会影响整个工程进度。

在 AOE 网中，从源点到汇点的带权路径长度最大的路径为关键路径。关键路径上的活动为关键活动。

二 四个核心概念

确定关键路径要弄清楚四个概念：事件的最早发生时间、最迟发生时间，以及活动的最早发生时间、最迟发生时间。

1 事件 Vi 的最早发生时间 ve[i]

考察入边，求（弧尾 Ve + 入边权值）的最大值

2 事件 Vi 的最迟发生时间 vl[i]

考察出边，求（弧头 Vl - 出边权值）的最小值

3 活动 ai=<Vj,Vk> 的最早发生时间 e[i]

弧尾的最早发生时间。

4 活动 ai=<Vj,Vk> 的最早发生时间 l[i]

弧头的最迟发生时间减去边值。

三 图解

下图是一个 AOE 网，求它的关键路径。

1 求拓扑排序序列，将其保存在 topo[] 数组中。

2 按照拓扑排序序列（0,2,1,3,4,5）,从前向后求解每个节点的最早发生时间 ve[]
ve[0]=0

v2[2]=ve[0]+15=15

ve[1]=max{ve[2]+4,ve[0]+2}=19

ve[3]=ve[1]+10=29

ve[4]=max{ve[2]+ve[1]+19}=38

ve[5]=max{ve[4]+5,ve[3]+6}=43

3 按照逆拓扑顺序（5,4,3,1,2,0），从后向前求解每个节点的最迟发生时间 vl[]。初始化汇点的最迟发生时间为汇点的最早发生时间，即 vl[n-1]=ve[n-1]。对其它节点考察出边，弧头 vl - 出边权值的最小值。

vl[5]=ve[5]=43

vl[4]=vl[5]-5=38

vl[3]=vl[5]-6=37

vl[1]=min{vl[4]-19,vl[3]-10}=19

vl[2]=min(vl[4]-11,vl[1]-4)=15

vl[0]=min{vl[2]-15,vl[1]-2}=0

计算完成后，事件的最早发生时间和最迟发生时间如下表所示。

| <br>事件<br> | <br>ve[i]<br> | <br>vl[i]<br> |
| <br>0<br> | <br>0<br> | <br>0<br> |
| <br>1<br> | <br>19<br> | <br>19<br> |
| <br>2<br> | <br>15<br> | <br>15<br> |
| <br>3<br> | <br>29<br> | <br>37<br> |
| <br>4<br> | <br>38<br> | <br>38<br> |
| <br>5<br> | <br>43<br> | <br>43<br> |

4 计算每个活动最早发生时间和最迟发生时间。

• 活动a0=<V0,V1>：e[0]=ve[0]=0；l[0]=vl[1]-2=17
• 活动a1=<V0,V2>：e[1]=ve[0]=0；l[1]=vl[2]-15=0
• 活动a2=<V2,V1>：e[2]=ve[2]=15；l[2]=vl[1]-4=15
• 活动a3=<V1,V3>：e[3]=ve[1]=19；l[3]=vl[3]-10=27
• 活动a4=<V1,V4>：e[4]=ve[1]=19；l[4]=vl[4]-19=19
• 活动a5=<V2,V4>：e[5]=ve[2]=15；l[5]=vl[4]-11=27
• 活动a6=<V3,V5>：e[6]=ve[3]=29；l[6]=vl[5]-6=37
• 活动a7=<V4,V5>：e[7]=ve[4]=38；l[7]=vl[5]-5=38

如果活动的最早发生时间等于最迟发生时间，则该活动为关键活动

| <br>活动<br> | <br>e[i]<br> | <br>l[i]<br> | <br>关键活动<br> |
| <br>a0<br> | <br>0<br> | <br>17<br> | <br> |
| <br>a1<br> | <br>0<br> | <br>0<br> | <br>是<br> |
| <br>a2<br> | <br>15<br> | <br>15<br> | <br>是<br> |
| <br>a3<br> | <br>19<br> | <br>27<br> | <br> |
| <br>a4<br> | <br>19<br> | <br>19<br> | <br>是<br> |
| <br>a5<br> | <br>15<br> | <br>27<br> | <br> |
| <br>a6<br> | <br>28<br> | <br>37<br> | <br> |
| <br>a7<br> | <br>38<br> | <br>38<br> | <br>是<br> |

5 由关键活动组成的从源点到汇点的关键路径 V0-V2-V1-V4-V5

四 算法步骤

1 利用拓扑排序算法，将拓扑排序结果保存在 topo[] 数组中。

2 将每个时间的最早发生时间都初始化 0，即 v[i]=0,i=0,1,2...n-1

3 根据拓扑顺序从前向后依次求每个事件的最早发生时间，循环执行这些操作：a 取出拓扑序列中的节点 k；b 用指针 p 依次指向 k 的每个邻接点，取得邻接点的序号 j=p.v,更新节点 j 的最早发生时间 ve[j]

if(ve[j]<ve[k]+p.weight)  ve[j]=ve[k]+p.weight

4 将每个时间的最迟发生时间 vl[i] 都初始化为汇点的最早发生时间，即 vl[i]=ve[n-1]

5 按照逆拓扑顺序从后向前求解每个事件的最迟发生时间，循环执行这些操作：a 取出逆拓扑序列中的序号 k；b 用指针 p 依次指向 k 的每个邻接点，取得邻接点序号 j=p.v，更新节点 k 的最迟发生时间 vl[k]

if(vl[k]>vl[j]-p.weight) vl[k]=vl[j]-p.weight

6 判断活动是否为关键活动。瑞昱每个节点i，都用指针p依次指向 i 的每个邻接点，取得邻接点的序号 j=p.v,计算活动<Vi,Vj>的最早发生时间和最迟发生时间，如下图所示，如果 e 和 l 相等，则活动<Vi，Vj>为关键活动。