算法分析2013设计qiu-lec

1、1递归解(Recursive Solution)lij(m) = weight of shortest path i jt contains at most medges(lij(m)从i到j至多含有m条边的最短路径的权)at most m edges0if i = jm = 0: lij(0) = if i jjikm 1: lij(m) = min lik+ wkj(m-1)1 k nShortest path from i to j wt most m 1 edges(从i到j的最短路径含有 m 1条边)Shortest path from i to j containing at mo

2、st m edges, considering all sible prede sors (k) of j (从i到j的最段路径含有m 条边, 考虑所有j的先前顶点k的情况)6最短路径的优化结构(Optimal Substructure of a Shortest Path)at most m edgesAll subpaths of a shortest pathare shortest paths (最短路径的部分路径必然是最短的)ij kLet p: a shortest path p fromat most m - 1 edgesvertex i to jt contains atmo

3、st m edges (p是从i到j至多 If i j: p = i p k j含有m条边的最短路径) p has at most m-1 edges(p至多有m-1条边)If i = j (如果i = j, w(p) = 0) p is a shortest path(p是最短 w(p) = 0 and p has no edges的)(i, j) = (i, k) + wkj5全成对最短路径(All-Pairs Shortest Paths)Ame the graph (G) is given as2adjacency matrix of weights34 W = (w ), n x n

4、 matrix, |V| = n183ij2 Vertinumbered 1 to n-471 -50if i = j564wij =weight of (i, j) if i j , (i, j) Eif i j , (i, j) E(邻接矩阵表示, n x n矩阵, 元素值如上定义)Output the result in an n x n matrix(输出n x n矩阵D = (dij) D = (dij), where dij = (i, j)Solve the problem using dynamic programming (动态规划4?)全成对最短路径解决方案(All-Pai

5、rs Shortest Paths Solutions)Run BELLMAN-FORD once from each vertex:(对于每一个顶点, 运行BELLMAN-FORD(单源最短)O(V2E), which is O(V4) if the graph is dense(E = (V2) (计算开销: O(V2E), 甚至 O(V4) )If no negative-weight edges, could run Dijkstras algorithm once from each vertex: (如果不存在负权值边, 可利用Dijkstras算法计算单源最短)O(VElgV)

6、with binary heap, O(V3lgV) if the graph is dense (计算开销:O(VElgV), 甚至 O(V3lgV)：对于边稠密的图 )We can solve the problem in O(V3), with no elaborate datastructures. (可以设计O(V3)开销的全成对最短路径算法，且不需要特殊的数据结构)3全成对最短路径(All-Pairs Shortest Paths)Given:(输入)2Directed graph G = (V, E) (有向图)34Weight function w : E R (权)1832C

7、ompute: (计算)-471 -5The shortest paths betn all pairs of54vertiin a graph (图中任何点对之间的最6短距离)Represen ion of the result: ann n matrix of shortest-path distan(u, v) (结果表示: n n矩阵, 元素是对应的点对之间的最短距离(u, v) )2算法设计与分析Algorithms Design &ysis第十三讲：全成对最短路径华技大学学院主讲12改进运行时间(Improving Running Time)No need to compute a

8、ll L(m) matri(不必计算所有L(m) )If no negative-weight cycles exist: (如果没有负回路, 则有:)L(m) = L(n - 1) for all m n 1We can compu(n-1) by computing the sequence: (因此可以通过计算下列序列来计算L(n-1) )L(1) = WL(2) = W2 = W WL(4) = W4 = W2 W2L(8) = W8 = W4 W4 2x n 1Ln1 W 2lg( n1) 12(m) = min l (m-1) + w lijikkj1 k n2L(m-1) = L

9、(1)W348123-471 -5564L(m) = L(2) and so on until L(4)110382-430-417405112-1-50-28160038-4017402-5060038-4017402-5060成对最短路径算法:SLOW-ALL-PAIRS- SHORTEST-PATHS(W, n)1. L(1) Wfor m 2 to n - 1do L(m) EXTEND (L(m - 1), W, n)return L(n - 1)Running time: (n4)10延伸算法:EXTEND(L, W, n)crea, an n n matrixfor i 1 to

10、 nl (m) = min l (m-1) + w do for j 1 to nij1 k nikkjdo lij for k 1 to ndo lij min(lij, lik + wkj)return LRunning time: (n3)9最短路径的延伸(Extending the Shortest Path)l (m) = min l (m-1) + w ijikkj1 k nkjji*k=iL(m-1)n x nWL(m)Replace:min +Computing L(m) looks l ke+ matrix multiplication(计算与矩阵乘法相似)8计算最短路径(C

11、omputing the Shortest Paths)m = 1: lij(1) =wijL(1) = WThe path betn i and j is restricted to 1 edge (i到j只有1条边)Given W = (wij), compute: L(1), L(2), , L(n-1), where(m)(1) (2)(n-1)L(m) = (lij ) (给出W = (wij), 计算L , L , , L)L(n-1) contains the actual shortest-path weights (L(n-1)包含最短路径) Given L(m-1) and

12、 W compu(m) (计算过程: 给出L(m-1)和W, 求L(m) )Extend the shortest paths computed so far by one more edge (每次给当前的最短路径增加一条边)If the graph has no negative cycles: all simple shortest paths contain at most n - 1 edges (如果没有负权回路, 所有的最短路径至多含有n - 1条边, 因此有)(n-1)(n) (n+1)(n-1)(i, j) = lijand lij , l j . . .= lij73最短路

13、径结构(The Structure of a Shortest Path)k is not an ermediate vertex of path p (顶点k不是路径p的中间节点)kShortest path from i to j with ermediateijvertifrom 1, 2, , k is a shortest path from i to j with ermediate vertifrom 1, 2, , k - 1 (从i到j的中间节点来自1, 2, , k的最短路径即是从i到j的中间节点来自1, 2, , k - 1的最短路径)k is an ermediate

14、vertex of path p(顶点k是路 p1kp2径p的中间节点)jip1 is a shortest path from i to k(p1从i到k)p2 is a shortest path from k to j (p2从k到j)k is not ermediary vertex of p1, p2(k不是p1, p2的中间节点)p1 and p2 are shortest paths (是最短路径)18Exledij(k) = the weight of a shortest path from vertex i to vertex j will ermediary vertid

15、rawn from 1, 2, , k (dij(k) ：从i到j的路径的权值, 中间节点来自集合1, 2, , k )d13(0) =d13(1) = 6d13(2) = 5d13(3) = 5d13(4) = 4.517最短路径结构(The Structure of a Shortest Path)For any pair of vertii, j V, consider all paths from i to j whose ermediate vertiare all drawn from a subset 1, 2, , k (对于任何点对i和j, 考虑所有从i到j的路径, 这些路径

16、的中间节点来自集合1, 2, , k ) Find p, a minimum-weight path from these paths (从这些路径中确定最短路径p)p1ipujptNo vertex on these paths has index k这些路径不存在标号 k的顶点16最短路径结构(The Structure of a Shortest Path)Vertiin G are given byV = 1, 2, , n630.5(图G中的顶点)1234Consider a path p = v1, v2, , vl (对于212路径p = v1, v2, , vl )5 An e

17、rmediate vertex of p is any vertex in the set v2, v3, , vl-1 (p的中间顶点是集合v2, v3, , vl-1中的点) E g p = 1, 2, 4, 5: 2, 4p = 2, 4, 5: 415Floyd-Warshall 算法Given:给定2Directed, weighted graph G = (V, E)34(有向图G = (V, E)813Negative-weight edges may be present (可2以存在负权边)-471 -5No negative-weight cycles could be p

18、resent564he graph (但不能出现负权回路)Compute: 计算The shortest paths betn all pairs of vertiin a graph (点对之间的最短距离)14快速算法:FASTER-APSP(W, n)1. L(1) W2. m 1while m n - 1do L(2m) EXTEND(L(m), L(m), n)m 2mreturn L(m)OK to overshoot: products dont change after L(n - 1) (L(n - 1)后积不变化)Running Time: (n3lg n) (运行开销)13

19、4(k) = min d (k-1) , d (k-1) + d (k-1) dijijikkjD(0) = WD(1)21 2 3 4 51 2 3 4 53411813 222-471 -5 3356444D(2)551 2 3 4 5D(3)D(4)12345403-14-430-41-1740532-1-50-2851600384-4017405112-1-50-2600384-4017405 1125-50-260038-40174025-50-260038-4017402-5060算法:FLOYD-WARSHALL(W)1. n rowsW2. D(0) Wfor k 1 to n

20、do for i 1 to ndo for j 1 to n6.do d (k) min (d (k-1), d (k-1) + d (k-1) ijijikkj7. return D(n)Running time: (n3)23计算方法(Computing the Shortest Path Weights)d (k) =wif k = 0ijijmin d (k-1) , d (k-1) + d (k-1) if k 1ijikkjThe final solution: D(n) = (d (n): (最终解)ijd (n) = (i, j) i, j Vijjj+(k, j)ii(i, k)D(k-1)D(k)22递归解: A Recursive Solution (cont.)d (k) = the wei