AOE-网关键路径-Toy模板网

这篇具有很好参考价值的文章主要介绍了AOE-网关键路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

关键路径：在AOE-网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。
关键活动：关键路径上的活动称为关键活动。
关键路径可能不只一条，重要的是找到关键活动

事件Vi 的最早可能开始时间Ve(i)
是从源点V0 到顶点Vi 的最长路径长度。
Ve(i) =Max{Ve(k)+wk,i}（k是i的前驱事件）
wk,i是弧<Vk,Vi>的权值,即活动持续时间
事件Vi 的最迟允许开始时间Vl(i)
Vl(i)不得迟于其后继事件Vj的最迟发生时间减去活动 <Vi,Vj>
Vl(i) = Min{Vl(j) - wi,j}
活动ak 的最早可能开始时间 e(k)
设活动ak 在边< Vi , Vj >上，
e(k) = Ve(i)。
活动ak 的最迟允许开始时间 l(k)
l(k)需要保证不会引起后继事件Vj的Vl(j)延误
l(k) =Vl(j) - wi,j
l(k) == e(k)表示活动ak 是没有时间余量的关键活动。

步骤：
（1）对AOE-网中的顶点进行拓扑排序，按拓扑序列求出Ve(i)
（2）按逆拓扑序列求出Vl(i)
（3）求出e(k)和l(k)
（4）找出关键活动，从源点到汇点由关键活动形成的路径即关键路径

AOE-网关键路径

计算Ve(i)

Ve(0)=0
Ve(1)=Max{Ve(0)+w0,1}=6
Ve(2)=Max{Ve(0)+w0,2}=4
Ve(3)=Max{Ve(0)+w0,3}=5
Ve(4)=Max{Ve(1)+w1,4，Ve(2)+w2,4}=7
Ve(5)=Max{Ve(3)+w3,5}=7
Ve(6)=Max{Ve(4)+w4,6}=16
Ve(7)=Max{Ve(4)+w4,7，Ve(5)+w5,7}=14
Ve(8)=Max{Ve(6)+w6,8，Ve(7)+w7,8}=18

计算Vl(i)

Vl(8)=Ve(8)=18
Vl(7)=Min{Vl(8) - w7,8}=14
Vl(6)=Min{Vl(8) - w6,8}=16
Vl(5)=Min{Vl(7) - w5,7}=10
Vl(4)=Min{Vl(6) - w4,6，Vl(7) - w4,7}=7
Vl(3)=Min{Vl(5) - w3,5}=8
Vl(2)=Min{Vl(4) - w2,4}=6
Vl(1)=Min{Vl(4) - w1,4}=6
Vl(0)=Min{Vl(1) - w0,1，Vl(2) - w0,2，Vl(3) - w0,3}=0

计算e(i)
e(a1)=Ve(0)=0
e(a2)=Ve(0)=0
e(a3)=Ve(0)=0
e(a4)=Ve(1)=6
e(a5)=Ve(2)=4
e(a6)=Ve(3)=5
e(a7)=Ve(4)=7
e(a8)=Ve(4)=7
e(a9)=Ve(5)=7
e(a10)=Ve(6)=16
e(a11)=Ve(7)=14
计算l(i)
l(a11)=Vl(8) - w7,8=14
l(a10)=Vl(8) - w6,8=16
l(a9)=Vl(7) - w5,7=10
l(a8)=Vl(7) - w4,7=7
l(a7)=Vl(6) - w4,6=7
l(a6)=Vl(5) - w3,5=8
l(a5)=Vl(4) - w2,4=6
l(a4=Vl(4) - w1,4=6
l(a3)=Vl(3) - w0,3=3
l(a2)=Vl(2) - w0,2=2
l(a1)=Vl(1) - w0,1=0