数据结构 第七章-图.ppt

关键路径算法步骤： （1）从开始点v1出发，令ve(1)=0,按拓朴排序序列求其它各顶点的最早发生时间 ve(k)=max{ve(j)+dut(j,k)} (vj为以顶点vk为弧头的所有弧的弧尾 对应的顶点集合) V2 V1 V6 V3 V4 V5 V7 V8 V9 顶点 ve(i) vl(i) v1 0 v2 6 v3 4 v4 5 v5 7, 5 v6 7 v7 16 v8 14, 11 v9 18,18 该表次序为一拓扑排序序列 关键路径算法步骤： （2）从完成点vn出发，令vl(n)=ve(n),按逆拓朴排序序列求其它各顶点的最迟发生时间 Vl(j)=min{vl(k)-dut(j,k)} (vk为以顶点vj为弧尾的所有弧的弧头 对应的顶点集合) V2 V1 V6 V3 V4 V5 V7 V8 V9 顶点 ve(i) vl(i) v1 0 0，2，3 v2 6 6 v3 4 6 v4 5 8 v5 7 7，7 v6 7 10 v7 16 16 v8 14 14 v9 18 18 关键路径算法步骤： （3）求每一项活动ai(vj,vk): e(i)=ve(vj) l(i)=vl(vk)-dut(ai) 活动 e(i) l(i) l(i)-e(i) a1 0 0 0 a2 0 2 2 a3 0 3 3 a4 6 6 0 a5 4 6 2 a6 5 8 3 a7 7 7 0 a8 7 7 0 a9 7 10 3 a10 16 16 0 a11 14 14 0 V2 V1 V6 V3 V4 V5 V7 V8 V9 顶点 ve(i) vl(i) v1 0 0 v2 6 6 v3 4 6 v4 5 8 v5 7 7 v6 7 10 v7 16 16 v8 14 14 v9 18 18 V2 V1 V6 V3 V4 V5 V7 V8 V9 关键活动：选取e(i)=l(i)的活动。 关键路径： （1） v1? v2 ? v5 ? v7 ? v9 （2） v1? v2 ? v5 ? v8 ? v9 7.6 最短路径 7.6.1 从某个源点到其余各顶点的最短路径 V2 V0 V3 V1 V5 V4 5 30 50 10 10 60 始点 终点 最短路径 路径长度 v0 v1 无 v2 v0,v2 10 v3 v0,v4,v3 50 v4 v0,v4 30 v5 v0,v4,v3,v5 60 20 V2 V0 V3 V1 V5 V4 5 30 50 10 10 60 Dijkstra的路径长度递增次序产生最短路径法： ∞ 10 ∞ 30 100 V0 V0 V0 V0 V0 ∞ ∞ 10 ∞ 30 100 ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞ ∞ 50 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 10 ∞ ∞ ∞ 20 ∞ 60 ∞ ∞ ∞ ∞ ∞ ∞ 0 1 2 3 4 5 0 1 2 3 4 5 前驱顶点： 最短路径： 初始化 1 2 3 4 5 V2 V0 V3 V1 V5 V4 5 30 50 10 10 60 ∞ 10 ∞ 30 100 V0 V0 V2 V0 V0 +10 ∞ 10 60 30 100 ∞ ∞ 10 ∞ 30 100 ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞ ∞ 50 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 10 ∞ ∞ ∞ 20 ∞ 60 ∞ ∞ ∞ ∞ ∞ ∞ 0 1 2 3 4 5 0 1 2 3 4 5 前驱顶点： 最短路径： 比 较 大 小 1 2 3 4 5 20 V2 V0 V3 V1 V5 V4 5 30 50 10 10 60 ∞ 10 60 30 100 V0 V0 V4 V0 V4 +30 ∞ 10 50 30 90 ∞ ∞ 10 ∞ 30 100 ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞ ∞ 50 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 10 ∞ ∞ ∞ 20