1、1、求下圖從事件0出發(fā)的關(guān)鍵路徑，要求詳細(xì)過(guò)程。56785531410109124a12a6a8a11a5a2a13a10a4a1a9a7a318a008763142591、事件Vj可能的最早發(fā)生時(shí)間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)+weig

2、ht()=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可能的最晚發(fā)生時(shí)間vl(i) Vl(9)=48; Vl(8)=vl(9)-weight()=48-18=30; Vl(7)=vl(8)-weight()=30-8=22; Vl(6

3、)=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)-we

4、ight(),vl(2)-weight(),vl(3)-weight()= Min28-5,28-9,14-14=min23,19,0=0;3、活動(dòng)a(k)=的最早開(kāi)始時(shí)間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、活動(dòng)a(k)的最晚開(kāi)始時(shí)間L(k)L(0

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

6、1)=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、題中圖的關(guān)鍵路徑如下圖所示：0367892、對(duì)于下圖所示的有向圖，試?yán)肈ijkstra算法求源點(diǎn)1到其他各頂點(diǎn)的最短路徑，可參考教材P207圖7.29中的表格形式給出計(jì)算過(guò)程。從V1到各定點(diǎn)的D值和最短路徑的求解過(guò)程終點(diǎn)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,v2