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

1、求下图从事件0出发的关键路径，要求详细过程。

1、事件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)=max{ve(2)+weight(<v2,v5>),ve(4)+weight(<v4,v5>)}=max{9+10,9+6}=19; Ve(6)=ve(3)+weight(<v3,v6>)=14+3=17;

Ve(7)=max{ve(3)+weight(<v3,v7>),ve(6)+weight(<v6,v7>)}=max{14+7,17+5}=22; Ve(8)=max{ve(6)+weight(<v6,v8>),ve(7)+weight(<v7,v8>)}=max{17+5,22+8}=30; Ve(9)=max{ve(4)+weight(<v4,v9>),ve(5)+weight(<v5,v9>),ve(8)+weight(<v8,v9>)}= Max{9+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)=min{ve(7)-weight(<v7,v6>),ve(8)-weight(<v8,v6>)}=min{22-5,30-5}=min{17,25}=17; Vl(5)=vl(9)-weight(<v5,v9>)=48-10=38;

Vl(4)=min{vl(5)-weight(<v4,v5>),vl(9)-weight(<v4,v9>)}=min{38-6,48-12}=min{32,36}=32; Vl(3)=min{vl(6)-weight(<v3,v6>),vl(7)-weight(<v3,v7>)}=min{17-3,22-7}=min{14,15}=14 Vl(2)=vl(5)-weight(<v2,v5>)=38-10=28; Vl(1)=vl(4)-weight(<v1,v4>)=32-4=28;

Vl(0)=min{vl(1)-weight(<v0,v1>),vl(2)-weight(<v0,v2>),vl(3)-weight(<v0,v3>)}= Min{28-5,28-9,14-14}=min{23,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)=5 E(4)=ve(2)=9 E(5)=ve(3)=14 E(6)=ve(3)=14 E(7)=ve(4)=9 E(8)=ve(6)=17 E(9)=ve(4)=9 E(10)=ve(5)=19 E(11)=ve(6)=17 E(12)=ve(7)=22 E(13)=ve(8)=30

4、活动a(k)的最晚开始时间L(k)

L(0)=vl(1)-weight(<v0,v1>)==28-5=23 L(1)=vl(2)-weight(<v0,v2>)==28-9=21 L(2)=vl(3)-weight(<v0,v3>)==14-14=0 L(3)=vl(4)-weight(<v1,v4>)==32-4=28 L(4)=vl(5)-weight(<v2,v5>)==38-10=28 L(5)=vl(6)-weight(<v3,v6>)==17-3=14 L(6)=vl(7)-weight(<v3,v7>)==22-7=15 L(7)=vl(5)-weight(<v4,v5>)==38-6=32 L(8)=vl(7)-weight(<v6,v7>)==22-5=17 L(9)=vl(9)-weight(<v4,v9>)==48-12=36 L(10)=vl9)-weight(<v5,v9>)==48-10=38 L(11)=vl(8)-weight(<v6,v8>)==30-5=34 L(12)=vl(8)-weight(<v7,v8>)==30-8=22 L(13)=vl(9)-weight(<v8,v9>)==48-18=30

L(0)-E(0)=23-0=23 L(1)-E(1)=21-0=21 L(2)-E(2)=0-0=0 L(3)-E(3)=28-5=23 L(4)-E(4)=28-9=19 L(5)-E(5)=14-14=0 L(6)-E(6)=15-14=1 L(7)-E(7)=32-9=23 L(8)-E(8)=17-17=0 L(9)-E(9)=36-9=27 L(10)-E(10)=38-19=19 L(11)-E(11)=34-17=17 L(12)-E(12)=22-22=0 L(13)-E(13)=30-30=0

5、题中图的关键路径如下图所示：

2、对于下图所示的有向图，试利用Dijkstra算法求源点1到其他各顶点的最短路径，可参考教材P207图7.29中的表格形式给出计算过程。

从 V1 到各定点的 D 值和最短路径的求解过程 终点 i=1 2 (v1,v2) 15 (v1,v3) ∞ V4 V5 ∞ 12 (v1,v2,v5) 32 (v1,v2,v6) v5 32 (v1,v2,v6) v3 30 (v1,v3,v6) v4 30 (v1,v3,v6) v6 i=2 i=3 i=4 i=5

V2 V3

15 (v1,v3) ∞

15 (v1,v3) 27 (v1,v2,v5,v4) 27 (v1,v2,v5,v4)

V6 Vj

∞ v2

S

{v1,v2}

{v1,v2,v5} {v1,v2,v3,v5}

{v1,v2,v

3,v4,v5}

{v1,v2,v3,v4,v5,v6