5-2.最短路问题 日:3#:3#:计
5-2. 最 短 路 问 题
、问题的提法及应用背景 (1)问题的提法—寻求网络中两点间 的最短路就是寻求连接这两个点的边的 总权数为最小的通路。(注意:在有向 图中,通路开的初等链中所有的弧 应是首尾相连的。) (2)应用背景—管道铺设、线路安排、 厂区布局、设备更新等
一、问题的提法及应用背景 （1）问题的提法——寻求网络中两点间 的最短路就是寻求连接这两个点的边的 总权数为最小的通路。（注意：在有向 图中，通路——开的初等链中所有的弧 应是首尾相连的。） （2）应用背景——管道铺设、线路安排、 厂区布局、设备更新等
最短路算法: 1.D氏标号法( Dijkstra) (1)求解思路从始点出发,逐步顺序 地向外探寻,每向外延伸一步都要求是最 短的。 (2)使用条件网络中所有的弧权均 非负,即wn20
二、最短路算法： 1． D氏标号法（Dijkstra） （1）求解思路——从始点出发，逐步顺序 地向外探寻，每向外延伸一步都要求是最 短的。 （2）使用条件——网络中所有的弧权均 非负，即 w ij 0
(3)选用符号的意义: ①标号P(固定标号或永久性标号) 从始点到该标号点的最短路权 ②标号(临时性标号) 从始点到该标号点的最短路权上界
（3）选用符号的意义： ①标号 P（固定标号或永久性标号） ——从始点到该标号点的最短路权。 ②标号 T（临时性标号） ——从始点到该标号点的最短路权上界
(4)计算步骤及例: 第一步:始点标上固定标号p(v)=0,其余各 点标临时性标号T(y)=0,≠1 第二步:考虑满足条件 ①(v1V)∈A的所有点,; ②ν具有T标号,即v∈S,S为7 标号点集。 修改v的7标号为mm{()p(n)+b1},并 将结果仍记为Ty)
（4） 计算步骤及例： min T(v j ), p(v1 ) + l 1 j j v v s s j j v (v1 ,v j ) A j v 第二步：考虑满足条件 ① 的所有点 ； ② 具有T 标号，即 ， 为T 标号点集。 修改 的T标号为 ，并 将结果仍记为T(vj ) ( ) 0 1 第一步：始点标上固定标号 p v = ,其余各 点标临时性标号 T(vj )=, j1;