《运筹学》课程教学资源（PPT课件讲稿）第五章 图与网络分析（5.2）最短路问题

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 )=, j1;

第三步:若网络图中已无7标号点,停止 计算。否则,令T(vn)=min(v) v;∈s 然后将V的T标号改成P标号,转入第 二步。 此时,要注意将第二步中的v改为vb

第三步：若网络图中已无T标号点，停止 计算。否则,令 , 然后将 的T 标号改成P 标号 ，转入第 二步。 此时，要注意将第二步中的 v1 改为 。 0 j v ( ) min ( ) 0 j v s j T v T v j  = 0 j v

例5-3用狄克斯拉算法 求解图5-1所示最短路问题。 4 5 3 图51例53网络图

例5-3 用狄克斯拉算法 求解图5-1所示最短路问题。 4 v1 v2 v3 v4 v6 v5 v7 2 2 5 6 1 4 1 3 4 1 2 图5-1 例5-3网络图

解:先将图5-1的网络用矩阵形式表示出来: V10 5 246 5 0 D 20246 10414 40 4120

解：先将图5-1的网络用矩阵形式表示出来:                       − − − − − − − − − − − − − − − − − − = 4 1 2 0 3 1 0 2 6 4 0 1 4 1 0 4 1 4 5 2 0 1 3 2 0 2 4 6 0 2 5 7 6 5 4 3 2 1 V V V V V V V D 1 v 2 v 3 v 4 v 5 v 6 v 7 v

步骤考察点T标号点集标号(表P标号) 6 2V. 2+ 2+ 3V2 M4……:x.…114+1 4+ 8 4 5+45÷5+ ≤ 8 5V 6≤1v5 6+ 8 6 5

步骤 考察点 T标号点集 标 号（ 表P标号） 1 v1 {v2，…，v7 } v1 v2 v3 v4 v5 v6 v7 0 - - - - - - 0+2 0+5 2 5 - - - - 2 3 4 5 6 v2 v3 v4 v5 v6 {v3，…，v7 } {v4，…，v7 } {v5，v6，v7 } {v5，v7 } 2+2 2+4 2+6 4 6 8 - - 4+1 4+3 5 8 7 - 5+4 5+1 5+4 8 6 9 6+2 8 8 {v7 } 8+1 8

反向追踪,得到最优路线: 3→V4-V v5 讨论:若先把v的标号改为永久性标号, 该怎麽继续作下去?

反向追踪，得到最优路线： v1 v2 v3 v4 v6 v7 v5 讨论：若先把v7的标号改为永久性标号， 该怎麽继续作下去？