关键路径和最短路径详解过程

1、1、求下图从事件0出发的关键路径，要求详细过程。56785531410109124a12a6a8a11a5a2a13a10a4a1a9a7a318a008763142591、事件Vj可能的最早发生时间ve(j) Ve(0)=0; Ve(1)=ve(0)+weight(<v0,v1>)=0+5=5; Ve(2)=ve(0)+weight(<v0,v2>)=0+9=9; Ve(3)=ve(0)+weight(<v0,v3>)=0+14=14; Ve(4)=ve(1)+weight(<v1,v4>)=5+4=9; Ve(5)=maxve(2)+weig

2、ht(<v2,v5>),ve(4)+weight(<v4,v5>)=max9+10,9+6=19; Ve(6)=ve(3)+weight(<v3,v6>)=14+3=17; Ve(7)=maxve(3)+weight(<v3,v7>),ve(6)+weight(<v6,v7>)=max14+7,17+5=22; Ve(8)=maxve(6)+weight(<v6,v8>),ve(7)+weight(<v7,v8>)=max17+5,22+8=30; Ve(9)=maxve(4)+weight(<v4,v9

3、>),ve(5)+weight(<v5,v9>),ve(8)+weight(<v8,v9>)= Max9+12,19+10,30+18=48;2、事件vi可能的最晚发生时间vl(i) Vl(9)=48; Vl(8)=vl(9)-weight(<v8,v9>)=48-18=30; Vl(7)=vl(8)-weight(<v7,v8>)=30-8=22; Vl(6)=minve(7)-weight(<v7,v6>),ve(8)-weight(<v8,v6>)=min22-5,30-5=min17,25=17; Vl(5)

4、=vl(9)-weight(<v5,v9>)=48-10=38; Vl(4)=minvl(5)-weight(<v4,v5>),vl(9)-weight(<v4,v9>)=min38-6,48-12=min32,36=32; Vl(3)=minvl(6)-weight(<v3,v6>),vl(7)-weight(<v3,v7>)=min17-3,22-7=min14,15=14 Vl(2)=vl(5)-weight(<v2,v5>)=38-10=28; Vl(1)=vl(4)-weight(<v1,v4>)=3

5、2-4=28; Vl(0)=minvl(1)-weight(<v0,v1>),vl(2)-weight(<v0,v2>),vl(3)-weight(<v0,v3>)= Min28-5,28-9,14-14=min23,19,0=0;3、活动a(k)=<vi,vj>的最早开始时间E(k) E(0)=ve(0)=0 E(1)=ve(0)=0 E(2)=ve(0)=0 E(3)=ve(1)=5E(4)=ve(2)=9E(5)=ve(3)=14 E(6)=ve(3)=14 E(7)=ve(4)=9 E(8)=ve(6)=17E(9)=ve(4)=9E(1

6、0)=ve(5)=19 E(11)=ve(6)=17 E(12)=ve(7)=22E(13)=ve(8)=304、活动a(k)的最晚开始时间L(k)L(0)=vl(1)-weight(<v0,v1>)=28-5=23L(1)=vl(2)-weight(<v0,v2>)=28-9=21L(2)=vl(3)-weight(<v0,v3>)=14-14=0L(3)=vl(4)-weight(<v1,v4>)=32-4=28L(4)=vl(5)-weight(<v2,v5>)=38-10=28L(5)=vl(6)-weight(<v3,

7、v6>)=17-3=14L(6)=vl(7)-weight(<v3,v7>)=22-7=15L(7)=vl(5)-weight(<v4,v5>)=38-6=32L(8)=vl(7)-weight(<v6,v7>)=22-5=17L(9)=vl(9)-weight(<v4,v9>)=48-12=36L(10)=vl9)-weight(<v5,v9>)=48-10=38L(11)=vl(8)-weight(<v6,v8>)=30-5=34L(12)=vl(8)-weight(<v7,v8>)=30-8=22L

8、(13)=vl(9)-weight(<v8,v9>)=48-18=30L(0)-E(0)=23-0=23L(1)-E(1)=21-0=21L(2)-E(2)=0-0=0L(3)-E(3)=28-5=23L(4)-E(4)=28-9=19L(5)-E(5)=14-14=0L(6)-E(6)=15-14=1L(7)-E(7)=32-9=23L(8)-E(8)=17-17=0L(9)-E(9)=36-9=27L(10)-E(10)=38-19=19L(11)-E(11)=34-17=17L(12)-E(12)=22-22=0L(13)-E(13)=30-30=05、题中图的关键路径如下图所示：0367892、对于下图所示的有向图，试利用Dijkstra算法求源点1到其他各顶点的最短路径，可参考教材P207图7.29中的表格形式给出计算过程。从V1到各定点的D值和最短路径的求解过程终点i=1i=2i=3i=4i=52V2(v1,v2)15 1515V3(v1,v3)（v1,v3）(v1,v3) 2727V4(v1,v2,v5,v4)(v1,v2,v5,v4) 12