Introduction to algorithms 6.046J/18,401J/SMA5503 Lecture 19 Prof erik demaine
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 19 Prof. Erik Demaine
Shortest paths Single-source shortest paths nonnegative edge weights Dijkstra's algorithm: O(E+ vlg n General Bellman-Ford: O(VE) DAg One pass of Bellman-Ford: O(+ E) All-pairs shortest paths Nonnegative edge weights Dijkstra's algorithm n times: O(VE+v2Ig n) General Three algorithms today c 2001 by Charles E Leiserson Introduction to Agorithms Day 32 L19.2
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.2 Shortest paths Single-source shortest paths • Nonnegative edge weights Dijkstra’s algorithm: O(E + V lg V) • General Bellman-Ford: O(VE) • DAG One pass of Bellman-Ford: O(V + E) All-pairs shortest paths • Nonnegative edge weights Dijkstra’s algorithm |V| times: O(VE + V 2 lg V) • General Three algorithms today
All-pairs shortest paths Input: Digraph G=(V, E), where v=n, with edge-weight function w: E>R Output: n x n matrix of shortest-path lengths 6(2 i for all i,j∈ IDEA #1 Run bellman-Ford once from each vertex Time =O(VZE Dense graph→O(4)time Good first try! c 2001 by Charles E Leiserson Introduction to Agorithms Day32L19.3
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.3 All-pairs shortest paths Input: Digraph G = (V, E), where |V| = n, with edge-weight function w : E → R. Output: n × n matrix of shortest-path lengths δ(i, j) for all i, j ∈ V. IDEA #1: • Run Bellman-Ford once from each vertex. • Time = O(V 2E). • Dense graph ⇒ O(V 4) time. Good first try!
Dynamic programming Consider the n x n adjacency matrix A=(a of the digraph, and define di m)=weight of a shortest path from i to that uses at most m edges Claim We have fo if i=j loo if i≠ and for m=1.2.. n-1 di(m)=mink dik (m-1)+ c 2001 by Charles E Leiserson Introduction to Agorithms Day 32 L19.4
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.4 Dynamic programming Consider the n × n adjacency matrix A = (aij) of the digraph, and define dij(0) = 0 if i = j, ∞ if i ≠ j; Claim: We have and for m = 1, 2, …, n – 1, dij(m) = mink{dik(m–1) + akj }. dij(m) = weight of a shortest path from i to j that uses at most m edges
Proof of claim d,i (m)=mingdik m-D)+aki) 1 edges Relaxation for kda,+ ikki then d tda+a ≤m-1 edges Note: No negative-weight cycles implies c 2001 by Charles E Leiserson Introduction to Agorithms Day 32 L19.5
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.5 Proof of claim dij ( m ) = min k { dik (m–1) + akj } ii j j M k’s ≤ m – 1 edges ≤ m – 1 edge s ≤ m – 1 edges ≤ m – 1 edges Relaxation! for k ← 1 to n do if dij > dik + akj then dij ← dik + akj Note: No negative-weight cycles implies δ ( i, j) = dij (n–1) = dij ( n) = dij (n+1) = L
Matrix multiplication Compute C=A·B, where C,A, and b are n×n matrices k=1 Time =0(n)using the standard algorithm What if we map“+”imin”and”->“+”? Cimino(aik+ buji Thus.Dm)=Dm-1)×A Identity matrix =I 0 0 c 2001 by Charles E Leiserson Introduction to Agorithms Day 32 L19.6
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.6 Matrix multiplication Compute C = A · B, where C, A, and B are n × n matrices: ∑ = = n k ij aik bkj c 1 . Time = Θ ( n 3) using the standard algorithm. What if we map “ + ” → “min” and “·” → “ +”? cij = min k { aik + bkj }. Thus, D ( m ) = D ( m–1) “ × ” A. Identity matrix = I = ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 0 0 0 = D 0 = ( dij(0) )
Matrix multiplication (continued) The(min, +)multiplication is associative, and with the real numbers it forms an algebraic structure called a closed semiring Consequently, we can compute D(1)=D0)·A=A1 0(2)=D D(n-1)=D(n-2)·A=A yielding D()=(&i, D) Time =o(n'n)=0(n). No better than n x B-F c 2001 by Charles E Leiserson Introduction to Agorithms Day 32 L19.7
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.7 Matrix multiplication (continued) The (min, +) multiplication is associative, and with the real numbers, it forms an algebraic structure called a closed semiring. Consequently, we can compute D(1) = D(0) · A = A1 D(2) = D(1) · A = A2 M M D(n–1) = D(n–2) · A = An–1 , yielding D(n–1) = (δ(i, j)). Time = Θ(n·n3) = Θ(n4). No better than n × B-F
Improved matrix multiplication algorithm Repeated squaring: A2k=Ak A' Compute A.A O(g n) squarings Note:An-1=An=An+1=… Time=o(nlgn To detect negative-weight cycles, check the diagonal for negative values in O(n) additional time c 2001 by Charles E Leiserson Introduction to Agorithms Day 32 L19.8
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.8 Improved matrix multiplication algorithm Repeated squaring: A2k = Ak × Ak. Compute A2, A4, …, A2lg(n–1) . O(lg n) squarings Time = Θ(n3 lg n). To detect negative-weight cycles, check the diagonal for negative values in O(n) additional time. Note: An–1 = An = An+1 = L
Floyd-warshall algorithm Also dynamic programming, but faster Define c, (k)= weight of a shortest path from i to i with intermediate vertices belonging to the set (1, 2,.,k Thus, 8(i,j=c (n). Also, Ciy c 2001 by Charles E Leiserson Introduction to Agorithms Day32L19.9
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.9 Floyd-Warshall algorithm Also dynamic programming, but faster! Define cij(k) = weight of a shortest path from i to j with intermediate vertices belonging to the set {1, 2, …, k}. ii ≤≤kk ≤≤kk ≤≤kk ≤≤kk jj Thus, δ(i, j) = cij(n). Also, cij(0) = aij
Floyd-warshall recurrence Ci()=mink ci(), cikk-D)+Ck(k-D) k (k-1) intermediate vertices in (1, 2,...,k c 2001 by Charles E Leiserson Introduction to Agorithms Dav32L19.10
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.10 Floyd-Warshall recurrence cij(k) = mink {cij(k–1), cik(k–1) + ckj(k–1)} ii jj k cij(k–1) cik(k–1) ckj(k–1) intermediate vertices in {1, 2, …, k}