详细讲解关键路径

1.AOE-网
与AOV网相对的就是AOE-网。其中，边表示活动。AOE-网是一个带权的有向无环图，其顶点表示事件，弧表示活动，权表示持续的时间。通常，AOE-网可以估算工程完成的时间

例如， 图6.28所示为一个有11项活动的AOE-网。其中有9个事件Vo,V1, …, V g , 每个事件表示在它之前的活动已经完成， 在它之后的活动可以开始。例如， $v_0$v0​表示整个工程开始，$v_8$v8​ 表示整个工程结束，$v_4$v4​表示$a_4$a4​ 和$a_5$a5​ 已经完成， $a_7$a7​和$a_8$a8​ 可以开始了。与每个活动相联系的数是执行该活动所需的时间， 比如， 活动$a_1$a1​需要6天， $a_2$a2​需要4天等。

AOE-网通常用来解决两个问题：
（1）估计该项工程完成至少需要多少时间
（2）判断哪些活动是影响工程进度的关键

由千整个工程只有一个开始点和一个完成点，故在正常的情况（无环）下， 网中只有一个入度为零的点， 称作源点， 也只有一个出度为零的点， 称作汇点。在AOE-网中， 一条路径各弧上的权值之和称为该路径的带权路径长度（后面简称路径长度）。要估算整项工程完成的最短时间， 就是要找一条从源点到 汇点的带权路径长度最长的路径， 称为关键路径 。关键路径上的活动叫做关键活动，这些活动是影响工程进度的关键， 它们的提前或拖延将使整个工程提前或拖延。

(1)事件$v_i$vi​的最早发生时间$ve(i)$ve(i)
进入事件$v_i$vi​的每 一活动都结束，$v_i$vi​才可发生， 所以$ve(i)$ve(i)是从源点到$v_i$vi​的最长路径长度。
求$ve(i)$ve(i)的值， 可根据拓扑顺序从源点开始向汇点递推。通常将工程的开始顶点事件$v_0$v0​的最早发生时间定义为 0, 即:
$ve(0)=0$ve(0)=0
$ve(i)=Max{ve(k)+w_{k,i}} <v_k,v_i>∈T,1<=i<=n-1$ve(i)=Maxve(k)+wk,i​<vk​,vi​>∈T,1<=i<=n−1