Dijkstra算法基本步骤： 算法基本步骤 算法基本步骤： 迭 代 Step 1: 开始，给vs以 P 标号，P(vs)=0, 开始， 标号， 1 其余各点给 T 标号 T(vi)=+∞. 计算实例：连接 ： 的最短路. 求 计算实例求连接 vs、vt 的最短路
- ∞
P T
v1 2
0 -
2
- ∞
一、网络无负权的最短路 ——Dijkstra算法 算法 本算法由Dijkstra于1959年提出，可用于求解指定 于 年提出， 本算法由 年提出 两点间的最短路， 两点间的最短路，或从指定点到其余各点的最短 路，目前被认为是求无负权网络最短路问题的最 好方法。 好方法。 算法的基本思路基于以下原理： 算法的基本思路基于以下原理： 原理 若序列v 的最短路， 若序列 s ,v1 ,…,vn是从 s到vn的最短路， , 是从v 则序列v 则序列 s ,v1 ,…,vn-1必为从 s到vn-1的最短路。 , 必为从v 的最短路。
2 -
v1 2
0 -
2
4 -
7
- 8 9 - 14 ∞
vs 4
5 1 v3
4 -
v2 3 4
5
v4 1
5 7
vt
v5
7 -
迭 Step 3: 比较所有具有 T 标号的点，把最小者改为 标号的点， 代 P 标号， P(vi)=min[T(vi)]. 即 标号， 4
2 -
v1 2
0 -
2
4 -
7
- 8 8 - 14
迭 Step 3: 比较所有具有 T 标号的点，把最小者改为 标号的点， 代 P 标号， P(vi)=min[T(vi)]. 即 标号， 1 当存在两个以上最小者时 可同时改为 标号。若 当存在两个以上最小者时,可同时改为 标号。 可同时改为P 全部点为P标号 则停止。否则用v 代替v 标号,则停止 全部点为 标号 则停止。否则用 i代替 i转step 2.
7
- ∞ - ∞
vs 4
5 1 v3
- ∞
v2 3 4
5
v4 1
5 7
vt
v5
- ∞
标号的点,考虑这样的点 迭 Step 2: 若 vi 为刚得到 P 标号的点 考虑这样的点 vj : (vi ,vj)∈E 且vj 为 T 标号。 标号。 ∈ 代 1 对vj的T 标号进行如下更改 j)=min[T(vj),P(vi)+wij] 标号进行如下更改T(v
10.3 最短路问题
• 最短路问题：在一个赋权图 上，给定两个顶 最短路问题：在一个赋权图G上 点u和 v，在所有连接顶点 和 v 的路中，寻找 和 ，在所有连接顶点u和 的路中， 路长最短的路（称为u和 最短路 最短路.） 路长最短的路（称为 和 v最短路 ） • u和 v最短路的路长也称为 和 v的距离 最短路的路长也称为u和 的距离-d(u,v). 和 最短路的路长也称为 最短路问题是网络理论中应用最广泛的问题之一. 最短路问题是网络理论中应用最广泛的问题之一 许多优化问题可以使用这个模型．如设备更新、 许多优化问题可以使用这个模型．如设备更新、 管道铺设、线路安排、厂区布局等. 管道铺设、线路安排、厂区布局等 我们曾介绍了最短路问题的动态规划解法， 我们曾介绍了最短路问题的动态规划解法，但某 些最短路问题(如道路不能整齐分段者 如道路不能整齐分段者)构造动态规 些最短路问题 如道路不能整齐分段者 构造动态规 划方程比较困准、而图论方法则比较有效。 划方程比较困准、而图论方法则比较有效。 有些最短路问题也可以求网络中某指定点到其余所 有结点的最短路、或求网络中任意两点间的最短路. 有结点的最短路、或求网络中任意两点间的最短路
标号的点,考虑这样的点 迭 Step 2: 若 vi 为刚得到 P 标号的点 考虑这样的点 vj : (vi ,vj)∈E 且vj 为 T 标号。 标号。 ∈ 代 3 对vj的T 标号进行如下更改 j)=min[T(vj),P(vi)+wij] 标号进行如下更改T(v
2 -
v1 2
0 -
2
4 -
7
Dijkstra算法基本思想 算法基本思想 算法 Dijkstra算法的基本思想是从 s出发，逐步地向外 算法的基本思想是从v 出发， 算法的基本思想是从 探寻最短路，采用标号法 标号法。 探寻最短路，采用标号法。 执行过程中，与每个点对应，记录下一个数（称 执行过程中，与每个点对应，记录下一个数（ 为这个点的标号），它或者表示从v ），它或者表示从 为这个点的标号），它或者表示从 s到该点的最短 路长（称为P标号），或者是从 标号），或者是从v 路长（称为 标号），或者是从 s到该点的最短路 长的上界（称为T标号 标号）。 长的上界（称为 标号）。 算法每一步都把某个顶点的T 标号改为P 标号， 算法每一步都把某个顶点的 标号改为 标号， 当终点v 标号时，计算结束。最多n-1步 当终点 t 得到 P 标号时，计算结束。最多 步。
2 -
v1 2
0 -
2
4 -
7
8 - 13 13
vs 4
5 1 v3
4 -
v2 3 4
5
v4 1
5 7
vt
v5
7 -
2 -
最短路
2
0 -
v1 2
4 -
7
8 13 -
vs 4
5 1 v3
4 -
v2 3 4
5
v4 1
5 7
vt
v5
7 -
• Dijkstra算法不仅找到了所求最短路，而且找 算法不仅找到了所求最短路， 算法不仅找到了所求最短路 点到其他所有顶点的最短路； 到了从 vs 点到其他所有顶点的最短路；这些最 短路构成了图的一个连通无圈的支撑子图， 短路构成了图的一个连通无圈的支撑子图，即 图的一个支撑树。 图的一个支撑树。
- 2 2 ∞ -
v1
0 -
2 vs 4 v3
- ∞ 4
2
5 - ∞
7
- ∞ - ∞
5 1
v2 3 4
5
v4 1
5 7
vt
v5
- ∞
全部T标号中 最小,令 记录路径(v 全部 标号中,T(v1)最小 令P(v1)=2,记录路径 s ,v1). 标号中 最小 记录路径
标号的点,考虑这样的点 迭 Step 2: 若 vi 为刚得到 P 标号的点 考虑这样的点 vj : (vi ,vj)∈E 且vj 为 T 标号。 标号。 ∈ 代 2 对vj的T 标号进行如下更改 j)=min[T(vj),P(vi)+wij] 标号进行如下更改T(v
2 -
v1 2
0 -
2
4 -
7
8 14 - 13
vs 4
5 1 v3
4 -
v2 3 4
5
v4 1
5 7
vt
v5
7 -
迭 Step 3: 比较所有具有 T 标号的点，把最小者改为 标号的点， 代 P 标号， P(vi)=min[T(vi)]. 即 标号， 5 当存在两个以上最小者时 可同时改为 标号。若 当存在两个以上最小者时,可同时改为 标号。 可同时改为P 全部点为P标号 则停止。否则用v 代替v 标号,则停止 全部点为 标号 则停止。否则用 i代替 i转step 2.
5
v4 1
5 7
vt
v5
7 7 - -
标号的点,考虑这样的点 迭 Step 2: 若 vi 为刚得到 P 标号的点 考虑这样的点 vj : (vi ,vj)∈E 且vj 为 T 标号。 标号。 ∈ 代 4 对vj的T 标号进行如下更改 j)=min[T(vj),P(vi)+wij] 标号进行如下更改T(v
首先， 标号， 解: (1)首先，给vs以 P 标号，P(vs)=0,其余各点给 T 标 首先 其余各点给 号 T(vi)=+∞. (2) 考察 s , T(v1)=min[T(v1),P(vs)+ws1]= min[+∞,0+2]=2 考察v T(v2)=min[T(v2),P(vs)+ws2]= min[+∞,0+5]=5 T(v3)=min[T(v3),P(vs)+ws3]= min[+∞,0+4]=4 (3) 全部 标号中 全部T标号中 标号中,T(v1)最小 令P(v1)=2,记录路径 s ,v1). 最小,令 记录路径(v 最小 记录路径 (4)考察 1 , T(v2)=min[T(v2),P(v1)+w12]= min[5,2+2]=4 考察v 考察 T(v4)=min[T(v4),P(v1)+w14]= min[+∞,2+7]=9 (5) 全部 T 标号中 标号中,T(v2),T(v3)最小 令P(v2)=4, P(v3)=4, 最小,令 最小 记录路径(v 记录路径 1 ,v2), (v1 ,v4),. .…………
Dijkstra算法步骤： 算法步骤 算法步骤： Step 1: 开始，给vs以 P 标号，P(vs)=0, 开始， 标号， 其余各点给 T 标号 T(vi)=+∞. Step 2: 若 vi 为刚得到 P 标号的点 考虑这样的点 标号的点,考虑这样的点 vj : (vi ,vj)∈E 且vj 为 T 标号。 标号。 ∈ 标号进行如下更改T(v 对vj的T 标号进行如下更改 j)=min[T(vj),P(vi)+wij] Step 3: 比较所有具有 T 标号的点，把最小者改为 标号的点， 即 P 标号， P(vi)=min[T(vi)]. 标号， 当存在两个以上最小者时,可同时改为 标号。 可同时改为P 当存在两个以上最小者时 可同时改为 标号。若 全部点为P标号 则停止。否则用v 代替v 标号,则停止 全部点为 标号 则停止。否则用 i代替 i转step 2.