终点 从v0到各终点的D值和最短路径的求解过程 i=1 i=2 ∞ i=3 ∞ i=4 ∞ i=5 ∞ 无 ∞ 10 (v0,v2)
V1 V2
V3 V4 ∞ 30 60 (v0,v2,v3) 30 50 (v0,v4,v3) (v0,v4) (v0,v4) V5 100 (v0,v5) Vj S V2 100 (v0,v5) V4 90 (v0,v4,v5) V3 {v0,v2,v3,v4} 60 (v0,v4,v3,v5) V5 {v0,v2,v3,v4,v5}
{v0,v2} {v0,v2,v4} 8. 图6-15给出了一个具有15个活动、11个事件的工程的AOE网，求关键路径。 v4 a7=6 a3=2 v7 v2 a4=1 a1=3 a11=7 a8=8
v5 v1 a9=4 a5=3 a2=4 v11 v3 v8 a12=4
a13=10 a15=6a6=5
v6 v1001
a10=2 v9 a14=1 图6-15 8. 求解过程如下：
①事件的最早发生时间ve[k]。 ve (1)=0 ve (2)=3 ve (3)=4
ve (4)=ve(2)+2=5
ve (5)=max{ve(2)+1,ve(3)+3}=7 ve (6)=ve(3)+5=9
ve (7)=max{ve(4)+6,ve(5)+8}=15 ve (8)=ve(5)+4=11
ve (9)=max{ve(8)+10,ve(6)+2}=21 ve (10)=max{ve(8)+4,ve(9)+1}=22 ve (11)=max{ve(7)+7,ve(10)+6}=28
②事件的最迟发生时间vl[k]。 vl (11)= ve (11)=28
vl (10)= vl (11)-6=22 vl (9)= vl (10)-1=21
vl (8)=min{ vl (10)-4, vl (9)-10}=11 vl (7)= vl (11)-7=21 vl (6)= vl (9)-2=19
vl (5)=min{ vl (7)-8,vl (8)-4}=7 vl (4)= vl (7)-6=15
vl (3)=min{ vl (5)-3, vl (6)-5}=4 vl (2)=min{ vl (4)-2, vl (5)-1}=6 vl (1)=min{vl (2)-3, vl (3)-4}=0
③活动ai的最早开始时间e[i]和最晚开始时间l[i]。
活动a1 e (1)=ve (1)=0 l (1)=vl (2) -3 =3 活动a2 e (2)=ve (1)=0 l (2)=vl (3) - 4=0 活动a3 e (3)=ve (2)=3 l (3)=vl (4) - 2=13 活动a4 e (4)=ve (2)=3 l (4)=vl (5) - 1=6 活动a5 e (5)=ve (3)=4 l (5)=vl (5) - 3=4 活动a6 e (6)=ve (3)=4 l (6)=vl (6) - 5=14 活动a7 e (7)=ve (4)=5 l (7)=vl (7) - 6=15 活动a8 e (8)=ve (5)=7 l (8)=vl (7) - 8=13 活动a9 e (9)=ve (5)=7 l (9)=vl (8) - 4=7 活动a10 e (10)=ve (6)=9 l (10)=vl (9) - 2=19 活动a11 e (11)=ve (7)=15 l (11)=vl (11) - 7=21 活动a12 e (12)=ve (8)=11 l (12)=vl (10) - 4=18 活动a13 e (13)=ve (8)=11 l (13)=vl (9) - 10=11 活动a14 e (14)=ve (9)=21 l (14)=vl (10) -1=21 活动a15 e (15)=ve (10)=22 l (15)=vl (11) -6 =22
④最后，比较e[i]和l[i]的值可判断出a2,a5,a9,a13,a14,a15是关键活动，关键路径如图6-18所示。
a9=4 v1 v5 v3 a2=4 a5=3 v11 v8 a15=6 a13=10 v9 v1001 a14=1
四、算法设计题
图6-18
1. 编写一个算法，求出邻接矩阵表示的无向图中序号为numb的顶点的度数。
int degree1(Graph & ga, int numb)