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

《关键路径和最短路径详解过程》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、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)=max{ve(2)+weight(),ve(4)+weight(

2、4,v5>)}=max{9+10,9+6}=19;Ve(6)=ve(3)+weight()=14+3=17;Ve(7)=max{ve(3)+weight(),ve(6)+weight()}=max{14+7,17+5}=22;Ve(8)=max{ve(6)+weight(),ve(7)+weight()}=max{17+5,22+8}=30;Ve(9)=max{ve(4)+weight(),ve(5)+weight(),ve(8)+weight()}=Max{9+12,19+10

3、,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)=min{ve(7)-weight(),ve(8)-weight()}=min{22-5,30-5}=min{17,25}=17;Vl(5)=vl(9)-weight()=48-10=38;Vl(4)=min{vl(5)-weight(),vl(9)-weight()}=min{38-6,

4、48-12}=min{32,36}=32;Vl(3)=min{vl(6)-weight(),vl(7)-weight()}=min{17-3,22-7}=min{14,15}=14Vl(2)=vl(5)-weight()=38-10=28;Vl(1)=vl(4)-weight()=32-4=28;Vl(0)=min{vl(1)-weight(),vl(2)-weight(),vl(3)-weight()}=Min{28-5,28-9,14-14}=min{23,19,0}=0;3、活动a(k)

5、=的最早开始时间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)-

6、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()=

7、=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)=1