最短路问题-D算法.ppt

最短路问题 一 问题的提法及应用背景 1 问题的提法 寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数最小的通路 注意 在有向图中 通路 开的初等链中所有的弧应是首尾相连的 2 应用背景 管道铺设 线路安排 厂区布局 设备更新等 二 最短路算法 1 D氏标号法 Dijkstra 边权非负2 列表法 福德法 有负权 无负回路 1 D氏标号法 Dijkstra 1 求解思路 从始点出发 逐步顺序地向外探寻 每向外延伸一步都要求是最短的 2 使用条件 网络中所有的弧权均非负 即 3 选用符号的意义 P标号 Permanent固定 永久性标号 从始点到该标号点的最短路权 T标号 Temporary临时性标号 从始点到该标号点的最短路权上界 4 计算步骤及例子 第一步 给起始点v1标上固定标号 其余各点标临时性标号T vj j 1 l1j 若网络图中已无满足此条件的T标号点 停止计算 第三步 令 然后将的T标号改成P标号 转入第二步 此时 要注意将第二步中的改为 例一 用Dijkstra算法求下图从v1到v6的最短路 解 1 首先给v1以P标号 给其余所有点T标号 2 例一 用Dijkstra算法求下图从v1到v6的最短路 4 5 6 反向追踪得v1到v6的最短路为 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 求从1到8的最短路径 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 min d12 d14 d16 min 0 2 0 1 0 3 min 2 1 3 1X 1 4 p4 1 p4 1 p1 0 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 4 min d12 d16 d42 d47 min 0 2 0 3 1 10 1 2 min 2 3 11 3 2X 1 2 4 p2 2 p1 0 p4 1 p2 2 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 min d16 d23 d25 d47 min 0 3 2 6 2 5 1 2 min 3 8 7 3 3X 1 2 4 6 p6 3 p2 2 p4 1 p1 0 p6 3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 min d23 d25 c47 d67 min 2 6 2 5 1 2 3 4 min 8 7 3 7 3X 1 2 4 6 7 p7 3 p2 2 p4 1 p1 0 p6 3 p7 3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 7 min d23 d25 d75 d78 min 2 6 2 5 3 3 3 8 min 8 7 6 11 6X 1 2 4 5 6 7 p5 6 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 7 min d23 d53 d58 d78 min 2 6 6 9 6 4 3 8 min 8 15 10 11 8X 1 2 3 4 5 6 7 p3 8 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 3 4 6 7 min d38 d58 d78 min 8 6 6 4 3 7 min 14 10 11 10X 1 2 3 4 5 6 7 8 p8 10 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 p8 10 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4