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

1、求下图从事件0出发的关键路径，要求详细过程。56785531410109124a12a6a8a11a5a2a13a10a4a1a9a7a318a008763142591、事件Vj可能的最早发生时间ve(j) Ve(0)=0; Ve(1)=ve(0)+weight()=0+5=5; Ve(2)=ve(0)+weight()=0+9=9; Ve(3)=ve(0)+weight()=0+14=14; Ve(4)=ve(1)+weight()=5+4=9; Ve(5)=maxve(2)+weight(),ve(4)+weight()=max9+10,9+6=19; Ve(6)=ve(3)+weight()=14+3=17; Ve(7)=maxve(3)+weight(),ve(6)+weight()=max14+7,17+5=22; Ve(8)=maxve(6)+weight(),ve(7)+weight()=max17+5,22+8=30; Ve(9)=maxve(4)+weight(),ve(5)+weight(),ve(8)+weight()= Max9+12,19+10,30+18=48;2、事件vi可能的最晚发生时间vl(i) Vl(9)=48; Vl(8)=vl(9)-weight()=48-18=30; Vl(7)=vl(8)-weight()=30-8=22; Vl(6)=minve(7)-weight(),ve(8)-weight()=min22-5,30-5=min17,25=17; Vl(5)=vl(9)-weight()=48-10=38; Vl(4)=minvl(5)-weight(),vl(9)-weight()=min38-6,48-12=min32,36=32; Vl(3)=minvl(6)-weight(),vl(7)-weight()=min17-3,22-7=min14,15=14 Vl(2)=vl(5)-weight()=38-10=28; Vl(1)=vl(4)-weight()=32-4=28; Vl(0)=minvl(1)-weight(),vl(2)-weight(),vl(3)-weight()= Min28-5,28-9,14-14=min23,19,0=0;3、活动a(k)=的最早开始时间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(10)=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()=28-5=23L(1)=vl(2)-weight()=28-9=21L(2)=vl(3)-weight()=14-14=0L(3)=vl(4)-weight()=32-4=28L(4)=vl(5)-weight()=38-10=28L(5)=vl(6)-weight()=17-3=14L(6)=vl(7)-weight()=22-7=15L(7)=vl(5)-weight()=38-6=32L(8)=vl(7)-weight()=22-5=17L(9)=vl(9)-weight()=48-12=36L(10)=vl9)-weight()=48-10=38L(11)=vl(8)-weight()=30-5=34L(12)=vl(8)-weight()=30-8=22L(13)=vl(9)-weight()=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) 12V5(v1,v2,v5) 32323030V6(v1,v