PDF《最短通路问题》

最短通路问题 离散数学图论初步 南京大学计算机科学与技术系 内容提要 ? 引言 ? Dijkstra算法 ? 旅行商问题(TSP) 带权图与最短通路问题 ? 带权图:三元组 (V, E, W),(V, E)是图,W是从E到 非负实数集的一个函数.

W(e)表示边e的权. ? 一条通路上所有边的权的和称为该通路的长度. ? 两点之间长度最小的通路称为两点之间的最短通路, 不一定是唯一的. ? 单源点最短路问题 给定带权图 G(V, E, W)并指定一个源点,确定该源 点到图中其它任一顶点的最短路(长度和路径). Dijkstra最短路径的算法思想(1959) ? 源点s到顶点v的最短路径若为s…uv, 则s…u是s到u 的最短路径. ? (n-1)条最短路径按照其长度的非减次序求得,设它 们的相应端点分别为u1, …un-1,最短路径长度记为 d(s, ui) , i=1,…n-1. ? 假设前i条最短路径已知,第(i+1)条最短路径长度: d(s, ui+1)=min{d(s, uj) +W(uj, ui+1)| j=1,…i} 求最短路径的Dijkstra算法 ? 输入:连通带权图G,|VG|=n, 指定顶点s?VG ? 输出:每个顶点v的标注(L(v), u), 其中: ? L(v)即从s到v的最短路径长度(目前可得的) ? u是该路径上v前一个顶点. 求最短路的一个例子 s

7 7

2 1

2 4

1 2

4 4

8 3

5 3

4 6

3 0 b a c d e f g h 求最短路的一个例子 s

7 7

2 1

2 4

1 2

4 4

8 3

5 3

4 6

3 0 1,c 2,c 8,c 7,c 4,c U1 b a c d e f g h s

7 7

2 1

2 4

1 2

4 4

8 3

5 3

4 6

3 0 1,c 2,c 8,c 7,c 4,c U2 b a c d e f g h 4,b S1 s

7 7

2 1

2 4

1 2

4 4

8 3

5 3

4 6

3 0 1,c 2,c 8,c 7,c 4,c U3 b a c d e f g h 4,b S2 3,e 6,e s

7 7

2 1

2 4

1 2

4 4

8 3

5 3

4 6

3 0 1,c 2,c 8,c 6,e 4,c b a c d e f g h U4 3,e 9,h S3 s

7 7

2 1

2 4

1 2

4 4

8 3

5 3

4 6

3 0 1,c 2,c 8,c 6,e 4,c b a c d e f g h U5 3,e 9,h S4 6,d 求最短路的一个例子(续) s

7 7

2 1

2 3

1 2

4 4

8 3

5 3

4 6

5 0

1 2

6 6

4 3

9 求最短路的一个例子(续) s

7 7

2 1

2 5

1 2

4 4

8 3

5 3

4 6

3 0 s

7 7

2 1

2 3

1 2

4 4

8 3

5 3

4 6

5 0

1 2

6 6

4 1

2 6

4 3

3 9

6 9 Dijkstra算法的描述 1.初始化:i=0, S0={s}, L(s)=0, 对其它一切v?VG, 将L(v) 置为?. 若n=1,结束. 2.?v?Si '=VG-Si, 比较L(v)和L(ui)+W(ui, v)的值 (ui?Si) 如果L(ui)+W(ui, v)