最短路问题__D算法.ppt

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