最短通路问题

回顾 欧拉通路/回路 欧拉图的充要条件 构造欧拉回路的Fleury算法 哈密尔顿通路/回路 哈密尔顿图的必要和充分条件 哈密尔顿图的应用

提要 引言 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前一个顶点。

求最短路的一个例子 2 b e 7 3 1 4 1 2 8 7 a c f h s 3 4 3 4 2 4 6 d g 5

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

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

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

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

S4 1,c 2,c 2 b e 7 3 1 4 1 2 8 6,e 7 a c f h s 3,e 8,c 6,d 3 U5 4 3 4 2 4 6 d g 5 9,h 4,c

求最短路的一个例子(续) s 7 2 1 3 4 8 5 6 9

求最短路的一个例子(续) 1 2 2 7 3 1 1 2 5 6 3 8 7 6 s 3 4 3 4 2 4 1 2 6 2 9 7 4 5 5 3 1 1 2 6 3 8 6 7 s 3 4 3 4 2 4 6 5 9 4

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)<L(v), 则将v的标注更新为(L(ui)+W(ui, v), ui)， 即： L(v)=min{ L(v), minuSi{L(u)+W(u,v)} } 3. 对所有Si'中的顶点，找出具有最小L(v)的顶点v, 作为ui+1 4．Si+1 = Si ⋃{ui+1} 5. i = i+1; 若i=n-1, 终止。否则：转到第2步。

Dijkstra算法的分析 可终止性 正确性 需证明当算法终止时 (这里d(s,v)是s到v的最短路径长度，即距离。) 复杂性 计数控制 L(v)=d(s, v)对一切v成立。 由标记中的诸ui确定的路径是一条最短路径 (这里d(s,v)是s到v的最短路径长度，即距离。) 复杂性 O(n2)

求所有结点间的最短距离？ Dijkstra算法： Floyd-Warshall 算法 |V|3 O(|V| |E| lg |V|) with binary heap — O(|V|3 lg |V|) if dense Floyd-Warshall 算法 |V|3

All-Pairs Shortest Paths Given a directed graph G = (V, E), weight function w : E → R, |V| = n. Assume no negative weight cycles. Goal: create an n × n matrix of shortest-path distances δ(u, v). We’ll see how to do in O(V3) in all cases, with no fancy data structure.

All Pairs Shortest Path – Floyd-Warshall Algorithm Dynamic programming approach. Use optimal substructure of shortest paths: Any subpath of a shortest path is a shortest path. Create a 3-dimensional table: Let dij(k) –shortest path weight of any path from i to j where all intermediate vertices are from the set {1,2, …, k}. Ultimately, we would like to know the values of dij(n).

Computing dij(k) Base condition: dij(0) = ? For k>0: dij(0) = wij. Let p=<vi, . . . , vj> be a shortest path from vertex i to vertex j with all intermediate vertices in {1,2, …, k}. If k is not an intermediate vertex, then all intermediate vertices are in {1,2, …, k-1}. If k is an intermediate vertex, then p is composed of 2 shortest subpaths drawn from {1,2, …, k-1}.

Recursive Formulation for dij(k)

Algorithm Running time = ? Memory required = ? O(n3). O(n2) (if we drop the superscripts).

Example

Step 1

Step 2

Step 3

Step 4

Step 5

旅行商问题 (Travelling Salesman Problem, TSP ) n个城市间均有道路，但距离不等，旅行商从某地出发，走过 其它n-1城市各一次，最后回到原地，如何选择最短路线？ 数学模型： 无向带权图G：顶点对应于城市，边对应于城市之间的道路， 道路长度用相应边的权表示。 问题的解：权最小的哈密尔顿回路。 G是带权完全图，总共有(n-1)!/2条哈密尔顿回路。因此， 问题是如何从这(n-1)!/2条中找出最短的一条。 (含25个顶点的完全图中不同的哈密尔顿回路有约3.11023条， 若机械地检查，每秒处理109条，需1千万年。)

旅行商问题 一个货郎（销售员）生活在城市a，假定访问的城市 是d, b, c，然后回到a，求完成这次访问的最短路径 的距离. b c a d 18 14 b c a d 11 10 12 7

旅行商问题 解：列出哈密尔顿回路, 并求其距离： （1）（abcda）=（12+7+11+18）= 48 （2）（acbda）=（14+7+10+18）= 49 （3）（abdca）=（12+10+11+14）= 47 18 14 b c a d 11 10 12 7

旅行商问题 哈密尔顿回路（路径）的最短路径问题 下面介绍一种最邻近算法： （1）选择任一顶点作为始点，找出离始点距离最小 的顶点，形成一条边的初始路径； （2）设u是最新加到这条路径上的顶点，从不在这条 路径上的所有顶点中选择一个与u距离最小的顶点, 把连接u与此结点的边加入路径中；重复执行直到G 中的各顶点均含在这条路径中。

旅行商问题 （3）把始点到最后加入的顶点的边放入路径中得到一条哈密尔顿回路，并为近似最短的哈密尔顿回路. b c a d 18 14 11 10 12 7

旅行商问题(TSP)的研究进展 （在最坏情况下）时间复杂性为多项式的算法？ （在最坏情况下）时间复杂性为多项式的近似算法 保证: WW’ cW (c=3/2), 误差为50 % 实际应用中，已有好的算法能够在几分钟内处理1000 个节点的规模，误差在2%

作业 见课程网站