最短路问题一、问题的提法及应用背景 一、问题的提法及应用背景 （ （ 1 1 ）问题的提法 ）问题的提法寻求网络中两点间 的最短路就是寻求连接这两个点的边的 总权数最小的通路。（注意：在有向图 中，通路 开的初等链 开的初等链中所有的弧应 是 首尾相连 首尾相连的。） （ （ 2 2 ）应用背景 ）应用背景管道铺设、线路安排 、厂区布局、设备更新等。二、最短路算法 二、最短路算法 1 1 D D 氏标号法（ 氏标号法（ Dijkstra Dijkstra ）；边权非负 ）；边权非负 2. 2. 列表法（福德法）；有负权，无负回路 列表法（福德法）；有负权，无负回路 4 v 1 v 2 v 3 v 4 v 6 v 5 v 7 2 2 5 6 1 4 1 3 4 1 21 1 D D 氏标号法（ 氏标号法（ Dijkstra Dijkstra ） ） （ （ 1 1 ）求解思路 ）求解思路从始点出发，逐步顺序 地向外探寻，每向外延伸一步都要求是 最 最 短的。 短的。 （ （ 2 2 ）使用条件 ）使用条件网络中所有的弧权均 非负 非负，即 。（ （ 3 3 ）选用符号的意义 ）选用符号
