AOE-网 关键路径

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

关键活动：关键路径上的活动称为关键活动。

关键路径可能不只一条，重要的是找到关键活动

事件Vi 的最早可能开始时间Ve(i)

是从源点V0 到顶点Vi 的最长路径长度。

Ve(i) =Max{Ve(k)+wk,i}（k是i的前驱事件）

wk,i是弧的权值,即活动持续时间

事件Vi 的最迟允许开始时间Vl(i)

Vl(i)不得迟于其后继事件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）找出关键活动，从源点到汇点由关键活动形成的路径即关键路径

计算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

由上易知，关键活动为a1，a4，a7，a8，a10，a11

有两条关键路径（a1，a4，a7，a10），（a1，a4，a8，a11）