文档介绍：动态规划 Dynamic Programming
6/25/2018
最短路问题
Dijkstra的标号法
图上作业
表上作业
6/25/2018
最短路问题的标号法
Dijkstra标号法:所有结点分为:
未标号:尚未标号(缺或写“∞”);
临时标号(T):从已永久标号的点一步可达的,比较后标“长”最小的数;
永久标号(P):所有当前已临时标号的结点中最小者改为“永久”,(加框)。
可从“起点”做起顺推,也可从“终点”一步一步地逆推。
6/25/2018
(顺走)
A
B1
B2
C1
C2
C3
D1
D2
E
3
6
4
4
4
4
3
2
5
5
3
1
2
2
0
4
3
6
9
7
5
10
9
8
9
12
3
5
6
8
7
9
12
4
最短路为:
A→B1→C1→D1→E
6/25/2018
12
(逆推)
A
B1
B2
C1
C2
C3
D1
D2
E
3
6
4
4
4
4
3
2
5
5
3
1
2
2
12
9
9
6
8
7
4
5
9
8
6
4
7
5
0
9
最短路为:
A→B1→C1→D1→E
10
13
6/25/2018
0
3
6 5 9
+∞+∞+∞
4
6 5 7
+∞+∞+∞
5
6
7 9 10
+∞
6
7 8 10
+∞
7
9 12
+∞
8
9
12
8 9
3
4
4
+∞+∞+∞
+∞+∞+∞
6/25/2018
小华家住在下图中①处,每天要到在⑨处的小
学上学,街道位置
及长度如图,请给
小华找一条最短上
学路线,并求出该
最短的路径之长。
1
9
6/25/2018
3
6
9
2
5
8
1
4
7
26 33
35 31 29
28 33
32 24 22
27 36
0
32
32
27
27
51
63
67
82
84
113
51
63
67
82
84
113
115
最短路:
①
↓
④
↓
⑤
↓
⑧
↓
⑨
总长:
113
6/25/2018
6/25/2018
0
3
4
3
9
5
8
4
8
5
6
7
7
6
14
9
11
14
7
10
13
8
12
9
16
15
10
13
12
13
13
18
16
18
7
最短路为:
A0→A1→B2→A3→B4→B5→A6
8
8
6/25/2018