《算法分析与设计 ch7》由会员分享，可在线阅读，更多相关《算法分析与设计 ch7（72页珍藏版）》请在金锄头文库上搜索。
1、6/10/2010 第七章第七章第七章第七章 图论算法图论算法图论算法图论算法 王宏志王宏志王宏志王宏志 计算机科学与工程系计算机科学与工程系计算机科学与工程系计算机科学与工程系 6/10/2010 7.1 7.1 最短路径问题最短路径问题最短路径问题最短路径问题 6/10/2010 单源最短路径 问题:给定一个有权的有向图G，找到从给 定源结点v到另一个结点v的最短路径。 6/10/2010 最短路径的性质 优化子结构: 最短路径包含最短子路径 证明: 如果某条子路径不是最短子路径 必然存在最短子路径 用最短子路径替换当前子路径 当前路径不是最短路径，矛盾! 6/10/2010 最短路径的性
2、质 (u,v) 是从u到v最短路径的权重 最短路径满足三角不等式: (u,v) (u,x) + (x,v) “证明”: x uv 这条路径不会比另外两条之和长这条路径不会比另外两条之和长 6/10/2010 最短路径的性质 如果图中包含负圈，某些最短路径可能不 存在 (Why?): du+w) then dv=du+w; 95 2 75 2 Relax 65 2 65 2 Relax 6/10/2010 Bellman-Ford 算法 BellmanFord() for each v V dv = ; ds = 0; for i=1 to |V|-1 for each edge (u,v) E
3、 Relax(u,v, w(u,v); for each edge (u,v) E if (dv du + w(u,v) return “no solution”; Relax(u,v,w): if (dv du+w) then dv=du+w 时间复杂性？时间复杂性？ 6/10/2010 Bellman-Ford 算法 BellmanFord() for each v V dv = ; ds = 0; for i=1 to |V|-1 for each edge (u,v) E Relax(u,v, w(u,v); for each edge (u,v) E if (dv du + w(u,
4、v) return “no solution”; Relax(u,v,w): if (dv du+w) then dv=du+w 初始化初始化d 松弛松弛: 进行进行|V|-1 轮轮, 松弛每条边松弛每条边 检验结果检验结果 何时得到解何时得到解? 6/10/2010 Bellman-Ford Algorithm BellmanFord() for each v V dv = ; ds = 0; for i=1 to |V|-1 for each edge (u,v) E Relax(u,v, w(u,v); for each edge (u,v) E if (dv du + w(u,v) r
5、eturn “no solution”; Relax(u,v,w): if (dv du+w) then dv=du+w 运行时间是多少？运行时间是多少？ A: O(VE) 6/10/2010 Bellman-Ford Algorithm BellmanFord() for each v V dv = ; ds = 0; for i=1 to |V|-1 for each edge (u,v) E Relax(u,v, w(u,v); for each edge (u,v) E if (dv du + w(u,v) return “no solution”; Relax(u,v,w): if
6、(dv du+w) then dv=du+w B E DC A -1 2 2 1 -3 5 3 4 s 6/10/2010 Bellman-Ford 注意到处理边的顺序影响到收敛速度 正确性:证明 |V|-1 轮之后dv = (s,v) 引理: dv (s,v) 总成立 起始显然 令v 是满足 dv Adj if (dv du+w(u,v) dv = du+w(u,v); 松弛步骤松弛步骤 Note: 调用了调用了 Q-DecreaseKey() B C DA 10 43 2 15 6/10/2010 Dijkstra 算法 Dijkstra(G) for each v V dv = ; ds
7、 = 0; S = ; Q = V; while (Q ) u = ExtractMin(Q); S = S U U u; for each v u-Adj if (dv du+w(u,v) dv = du+w(u,v); 运行时间是多少？运行时间是多少？ 6/10/2010 Dijkstra 算法 Dijkstra(G) for each v V dv = ; ds = 0; S = ; Q = V; while (Q ) u = ExtractMin(Q); S = S U U u; for each v u-Adj if (dv du+w(u,v) dv = du+w(u,v); A:
8、利用二叉堆利用二叉堆 O(E lg V) 利用利用Fibonacci堆堆 O(V lg V + E) 6/10/2010 Dijkstra 算法 Dijkstra(G) for each v V dv = ; ds = 0; S = ; Q = V; while (Q ) u = ExtractMin(Q); S = S U Uu; for each v u-Adj if (dv du+w(u,v) dv = du+w(u,v); 正确性正确性: 我们必须证明，当我们必须证明，当u从从Q中取出时，它已经收敛了中取出时，它已经收敛了 6/10/2010 Dijkstra 算法的正确性 dv (s
9、,v) v 令u是第一个选出的结点 s.t. 存在比 du更短的路径du (s,u) 令y是su真实最短路径上的第一个V-S的结点 dy = (s,y) du (s,u) = (s,y) + (y,u) (Why?) = dy + (y,u) dy但是如果 du dy, 则不会选择u. 矛盾 s x y u p2 p2 6/10/2010 任意两点最短路径任意两点最短路径 Problem: 找到图中每一对结点间最短路径找到图中每一对结点间最短路径 图可能包含负边但是不包含负圈图可能包含负边但是不包含负圈 表示：权矩阵表示：权矩阵 6/10/2010 图和权矩阵图和权矩阵 12345 10115
10、 29032 304 4203 530 v1v2 v3v4 v5 3 2 2 4 1 3 1 9 3 5 6/10/2010 子问题子问题 如何定义更小的问题？如何定义更小的问题？ 一种方法是将路径限制在仅包含一个有限一种方法是将路径限制在仅包含一个有限 集合中的结点集合中的结点 开始这个集合是空的开始这个集合是空的 这个集合可以一直增长到包含所有结点。这个集合可以一直增长到包含所有结点。 6/10/2010 子问题子问题 令令 D(k)i,j=从从vi到到 vj仅包含仅包含 v1,v2,vk 的路径。的路径。 D(0)=W D(n)=D 目标矩阵目标矩阵 如何从如何从D(k-1)计算计算 D
11、(k)? 6/10/2010 递归定义递归定义 因为因为 D(k)i,j= D(k-1)i,j or D(k)i,j= D(k-1)i,k+ D(k-1)k,j. 我们得到我们得到 D(k)i,j= min D(k-1)i,j, D(k-1)i,k+ D(k-1)k,j . Vi Vj Vk 仅包含 V1, . . . Vk -1 的最短路径 仅包含V1, . . . Vk的最短路径 6/10/2010 Floyd算法 1. D0 W /初始化D 2. P 0 / 初始化 P 3. for k 1 to n 4. do for i 1 to n 5. do for j 1 to n 6.if
12、(Dk-1 i, j Dk-1 i, k + Dk-1 k, j ) 7.then Dk i, j Dk-1 i, k + Dk-1 k, j 8.P i, j k; 9.else Dk i, j Dk-1 i, j 6/10/2010 例子 W = D0 = 405 20 -30 123 1 2 3 000 000 000 123 1 2 3 P = 1 2 3 5 -3 2 4 6/10/2010 D1 = 405 207 -30 123 1 2 3 000 001 000 123 1 2 3 P = 1 2 3 5 -3 2 4 D12,3 = min( D02,3, D02,1+D01
13、,3 ) = min (, 7) = 7 D13,2 = min( D03,2, D03,1+D01,2 ) = min (-3,) = -3 405 20 -30 123 1 2 3 D0 = 6/10/2010 D2 = 405 207 -1-30 123 1 2 3 000 001 200 123 1 2 3 P = D21,3 = min( D11,3, D11,2+D12,3 ) = min (5, 4+7) = 5 D23,1 = min( D13,1, D13,2+D12,1 ) = min (, -3+2) = -1 1 2 3 5 -3 2 4 D1 = 405 207 -3
14、0 123 1 2 3 6/10/2010 D3 = 205 207 -1-30 123 1 2 3 300 001 200 123 1 2 3 P = D31,2 = min(D21,2, D21,3+D23,2 ) = min (4, 5+(-3) = 2 32,1 = min(D22,1, D22,3+D23,1 ) = min (2, 7+ (-1) = 2 D2 = 405 207 -1-30 123 1 2 3 1 2 3 5 -3 2 4 6/10/2010 Floyd算法: 使用两个 D 矩阵 Floyd 1. D W 2. P 0 3. for k 1 to n / Computing D from D 4. do for i 1 to n 5. do for j 1 to n 6.if (D i, j D i, k + D k, j ) 7.then D i, j D i, k + D k, j 8.P i, j k; 9.else D i, j D i, j 10. Move D to D. 6/10/2010 Floyd算法：使用1个D Floyd 1. D W 2.
