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 k<1 to n do if d >da,+ 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