《关键路径和最短路径详解过程》由会员分享，可在线阅读，更多相关《关键路径和最短路径详解过程（4页珍藏版）》请在金锄头文库上搜索。
1、1、求下图从事件0出发的关键路径，要求详细过程。1事件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;V
2、e(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)-weig
3、ht()=48-10=38;Vl(4)=minvl(5)-weight(),vl(9)-weight()=min38-6,48-12=min32,36=32;Vl(3)=minvl(6)-weight(),v l(7)-weight()=min17-3,22-7=min14,15=14Vl(2)=vl(5)-weight()=38-10=28;Vl(1)=vl(4)-weight()=32-4=28;Vl(0)=minvl(1)-weight(),v l(2)-weight(),vl(3)-weight()=Min28-5,28-9,14-14=min23,19,0=0;3、活动a(k)=的最
4、早开始时间E(k)E(0)=ve(0)=0E(1)=ve(0)=0E(2)=ve(0)=0E(3)=ve(1)=5E(4)=ve(2)=9E(5)=ve(3)=14E(6)=ve(3)=14E(7)=ve(4)=9E(8)=ve(6)=17E(9)=ve(4)=9E(10)=ve(5)=19E(11)=ve(6)=17E(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)-w
5、eight()=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
6、)=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、题中图的关键路径如下图所示:2、对于下图所示的有向图，试利用Dijkstra算法求源点1到其他各顶点的最短路 径，可参考教材P207图7.29中的表格形式给出计算过程。终占八、从V1到各定点的D值和最短路径的求解过程12345V22 (v1,v2)V315 (v1,v3)15 (v1,v3)15 (v1,v3)V4oooo27 (v1,v2,v5,v4)27 (v1,v2,v5,v4)V5oo12 (v1,v2,v5)V6oo32 (v1,v2,v6)32 (v1,v2,v6)30 (v1,v3,v6)30 (v1,v3,v6)Vjv2v5v3v4v6Sv1,v2v1,v2,v5v1,v2,v3,v5v1,v2,v3,v4,v5v1,v2,v3,v4,v5,v6
