文档介绍：狄克斯屈拉（Dijkstra）标号算法
毕德春
辽东学院信息技术学院
1
整理课件
标号算法的基本原理回顾
如图v1→v2 →v3 →v5是v1 →v5的最短路，则v1 →v2 →v3一定是v1 →v3的最短路，v1 →v2 也一定是v1 →v2的最短路。
v1
v2
v3
v5
v4
2
10
1
5
3
7
8
2
整理课件
v1,6
v5
v2
2
3
4
6
4
v3
v1
v4
1
2
10
6
1
2
10
v8
v9
v7
2
3
6
3
v6
0,0
M, ∞
M, ∞
v1,3
M, ∞
M, ∞
M, ∞
v1,1
v1,1
永久标号
临时标号
例：用标号算法求v1出发到v8，使总费用最小的旅行路线。
标号算法计算过程示例
0,0
3
整理课件
v1,6
v5
v2
2
3
4
6
4
v3
v1
v4
1
2
10
6
1
2
10
v8
v9
v7
2
3
6
3
v6
0,0
M, ∞
M, ∞
v1,3
M, ∞
M, ∞
M, ∞
0,0
v1,1
v4,11
v1,3
标号算法计算过程示例
4
整理课件
v5
v2
2
3
4
6
4
v3
v1
v4
1
2
10
6
1
2
10
v8
v9
v7
2
3
6
3
v6
0,0
M, ∞
v1,1
M, ∞
M,∞
M, ∞
1,3
v4,11
v1,3
v1,6
v3,5
v3,5
标号算法计算过程示例
5
整理课件
v5
v2
2
3
4
6
4
v3
v1
v4
1
2
10
6
1
2
10
v8
v9
v7
2
3
6
3
v6
0,0
M, ∞
v4,11
v1,1
M, ∞
M, ∞
M, ∞
v1,3
v3,5
v2, 6
v2, 6
标号算法计算过程示例
6
整理课件
v5
v2
2
3
4
6
4
v3
v1
v4
1
2
10
6
1
2
10
v8
v9
v7
2
3
6
3
v6
0,0
M, ∞
v4,11
v1,1
M, ∞
M, ∞
v1,3
v5,12
v5,9
v5,9
v3,5
v2, 6
v5,10
标号算法计算过程示例
7
整理课件
v5
v2
2
3
4
6
4
v3
v1
v4
1
2
10
6
1
2
10
v8
v9
v7
2
3
6
3
v6
0,0
v5,10
v1,1
M, ∞
v5, 12
v1,3
v5,9
v3,5
v2, 6
v5,10
标号算法计算过程示例
8
整理课件
v5
v2
2
3
4
6
4
v3
v1
v4
1
2
10
6
1
2
10
v8
v9
v7
2
3
6
3
v6
0,0
v1,1
M, ∞
v5, 12
v1,3
v5,9
v3,5
v2, 6
v5,10
v5, 12
标号算法计算过程示例
9
整理课件
v5
v2
2
3
4
6
4
v3
v1
v4
1
2
10
6
1