最短路问题 D算法.ppt

最 短 路 问 题 一问题的提法及应用背景 1 问题的提法 寻求网络中两点间的最短路就是 寻求连接这两个点的边的 总权数最小的 通路 注意 在有向图中通路 开的初等链中所有的弧应是 首 尾相连 的 2 应用背景 管道铺设线路安排厂区布局 设备更新等 二最短路算法 1 D 氏标号法 Dijkstra 边权非负 2. 列表法福德法有负权无负回路 4 v 1 v 2 v 3 v 4 v 6 v 5 v