算法分析2013設(shè)計(jì)qiu-lec

1、1遞歸解(Recursive Solution)lij(m) = weight of shortest path i jt contains at most medges(lij(m)從i到j(luò)至多含有m條邊的最短路徑的權(quán))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(luò)的最短路徑含有 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(luò)的最段路徑含有m 條邊, 考慮所有j的先前頂點(diǎn)k的情況)6最短路徑的優(yōu)化結(jié)構(gòu)(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(luò)至多 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全成對(duì)最短路徑(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 (動(dòng)態(tài)規(guī)劃4?)全成對(duì)最短路徑解決方案(All-Pai

5、rs Shortest Paths Solutions)Run BELLMAN-FORD once from each vertex:(對(duì)于每一個(gè)頂點(diǎn), 運(yùn)行BELLMAN-FORD(單源最短)O(V2E), which is O(V4) if the graph is dense(E = (V2) (計(jì)算開(kāi)銷: O(V2E), 甚至 O(V4) )If no negative-weight edges, could run Dijkstras algorithm once from each vertex: (如果不存在負(fù)權(quán)值邊, 可利用Dijkstras算法計(jì)算單源最短)O(VElgV)

6、with binary heap, O(V3lgV) if the graph is dense (計(jì)算開(kāi)銷:O(VElgV), 甚至 O(V3lgV)：對(duì)于邊稠密的圖 )We can solve the problem in O(V3), with no elaborate datastructures. (可以設(shè)計(jì)O(V3)開(kāi)銷的全成對(duì)最短路徑算法，且不需要特殊的數(shù)據(jù)結(jié)構(gòu))3全成對(duì)最短路徑(All-Pairs Shortest Paths)Given:(輸入)2Directed graph G = (V, E) (有向圖)34Weight function w : E R (權(quán))1832C

7、ompute: (計(jì)算)-471 -5The shortest paths betn all pairs of54vertiin a graph (圖中任何點(diǎn)對(duì)之間的最6短距離)Represen ion of the result: ann n matrix of shortest-path distan(u, v) (結(jié)果表示: n n矩陣, 元素是對(duì)應(yīng)的點(diǎn)對(duì)之間的最短距離(u, v) )2算法設(shè)計(jì)與分析Algorithms Design &ysis第十三講：全成對(duì)最短路徑華技大學(xué)學(xué)院主講12改進(jìn)運(yùn)行時(shí)間(Improving Running Time)No need to compute a

8、ll L(m) matri(不必計(jì)算所有L(m) )If no negative-weight cycles exist: (如果沒(méi)有負(fù)回路, 則有:)L(m) = L(n - 1) for all m n 1We can compu(n-1) by computing the sequence: (因此可以通過(guò)計(jì)算下列序列來(lái)計(jì)算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成對(duì)最短路徑算法: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(計(jì)算與矩陣乘法相似)8計(jì)算最短路徑(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(luò)只有1條邊)Given W = (wij), compute: L(1), L(2), , L(n-1), where(m)(1) (2)(n-1)L(m) = (lij ) (給出W = (wij), 計(jì)算L , L , , L)L(n-1) contains the actual shortest-path weights (L(n-1)包含最短路徑) Given L(m-1) and

12、 W compu(m) (計(jì)算過(guò)程: 給出L(m-1)和W, 求L(m) )Extend the shortest paths computed so far by one more edge (每次給當(dāng)前的最短路徑增加一條邊)If the graph has no negative cycles: all simple shortest paths contain at most n - 1 edges (如果沒(méi)有負(fù)權(quán)回路, 所有的最短路徑至多含有n - 1條邊, 因此有)(n-1)(n) (n+1)(n-1)(i, j) = lijand lij , l j . . .= lij73最短路

13、徑結(jié)構(gòu)(The Structure of a Shortest Path)k is not an ermediate vertex of path p (頂點(diǎn)k不是路徑p的中間節(jié)點(diǎn))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(luò)的中間節(jié)點(diǎn)來(lái)自1, 2, , k的最短路徑即是從i到j(luò)的中間節(jié)點(diǎn)來(lái)自1, 2, , k - 1的最短路徑)k is an ermediate

14、vertex of path p(頂點(diǎn)k是路 p1kp2徑p的中間節(jié)點(diǎn))jip1 is a shortest path from i to k(p1從i到k)p2 is a shortest path from k to j (p2從k到j(luò))k is not ermediary vertex of p1, p2(k不是p1, p2的中間節(jié)點(diǎn))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(luò)的路徑的權(quán)值, 中間節(jié)點(diǎn)來(lái)自集合1, 2, , k )d13(0) =d13(1) = 6d13(2) = 5d13(3) = 5d13(4) = 4.517最短路徑結(jié)構(gòu)(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 (對(duì)于任何點(diǎn)對(duì)i和j, 考慮所有從i到j(luò)的路徑, 這些路徑

16、的中間節(jié)點(diǎn)來(lái)自集合1, 2, , k ) Find p, a minimum-weight path from these paths (從這些路徑中確定最短路徑p)p1ipujptNo vertex on these paths has index k這些路徑不存在標(biāo)號(hào) k的頂點(diǎn)16最短路徑結(jié)構(gòu)(The Structure of a Shortest Path)Vertiin G are given byV = 1, 2, , n630.5(圖G中的頂點(diǎn))1234Consider a path p = v1, v2, , vl (對(duì)于212路徑p = v1, v2, , vl )5 An e

17、rmediate vertex of p is any vertex in the set v2, v3, , vl-1 (p的中間頂點(diǎn)是集合v2, v3, , vl-1中的點(diǎn)) 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以存在負(fù)權(quán)邊)-471 -5No negative-weight cycles could be p

18、resent564he graph (但不能出現(xiàn)負(fù)權(quán)回路)Compute: 計(jì)算The shortest paths betn all pairs of vertiin a graph (點(diǎn)對(duì)之間的最短距離)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) (運(yùn)行開(kāi)銷)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計(jì)算方法(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