狄克斯屈拉(Dijkstra)标号算法.pptx

文档介绍：狄克斯屈拉（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
2
10
v8
v9
v7
2
3
6
3
v6
0,0
v5,10
v1,1
M, ∞
v5, 12
v1,3
v5,9
v5, 12
v3,5
v2, 6
v5,10
标号结束
反向追踪
v1 出发到 v8 总费用最小为12，旅行路线为 v1 ， v3 ， v 2， v5 ， v8
标号算法计算过程示例
10