Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 17 Prof. Erik Demaine Introduction to Algorithms Day 29 L17.2? 2001 by Charles E. Leiserson Paths in graphs Consider a digraph G = (V, E) with edge-weight function w : E →R. The weight of path p = v 1 → v 2 →L→ v k is defined to be ∑ ? = + = 1 1 1 ),()( k i ii vvwpw . v 1 v 1 v 2 v 2 v 3 v 3 v 4 v 4 v 5 v 5 4–2 –51 Example: w(p) = –2 Introduction to Algorithms Day 29 L17.3? 2001 by Charles E. Leiserson Shortest paths A shortest path from u to v is a path of minimum weight from u to v. The shortest- path weight from u to v is defined as δ(u, v) = min{w(p) : p is a path from u to v}. Note: δ(u, v) = ∞ if no path from u to v exists. Introduction to Algorithms Day 29 L17.4? 2001 by Charles E. Leiserson Optimal substructure Theorem. A subpath of a shortest path is a shortest path. Proof. Cut and paste: Introduction to Algorithms Day 29 L17.5? 2001 by Charles E. Leiserson Triangle inequality Theorem. For all u, v, x ∈ V, we have δ(u, v) ≤δ(u, x) + δ(x, v). u u Proof. x x v v δ(u, v) δ(u, x) δ(x, v) Introduction to Algorithms Day 29 L17.6? 2001 by Charles E. Leiserson Well-definedness of shortest paths If a graph G contains a negative-weight cycle, then some shortest paths may not exist. Example: u u v v … < 0 Introduction to Algorithms Day 29 L17.7? 2001 by Charles E. Leiserson Single-source shortest paths Problem. From a given source vertex s ∈ V, find the shortest-path weights δ(s, v) for all v ∈ V. If all edge weights w(u, v) are nonnegative, all shortest-path weights must exist. IDEA: Greedy. 1. Maintain a set S of vertices whose shortest- path distances from s are known. 2. At each step add to S the vertex v ∈ V – S whose distance estimate from s is minimal. 3. Update the distance estimates of vertices adjacent to v. Introduction to Algorithms Day 29 L17.8? 2001 by Charles E. Leiserson Dijkstra’s algorithm d[s] ← 0 for each v ∈ V –{s} do d[v] ←∞ S ←? Q ← V ? Q is a priority queue maintaining V – S while Q ≠? do u ← EXTRACT-MIN(Q) S ← S ∪ {u} for each v ∈ Adj[u] do if d[v] > d[u] + w(u, v) then d[v] ← d[u] + w(u, v) relaxation step Implicit DECREASE-KEY Introduction to Algorithms Day 29 L17.9? 2001 by Charles E. Leiserson Example of Dijkstra’s algorithm A B D C E 10 3 14 79 8 2 2 Graph with nonnegative edge weights: Introduction to Algorithms Day 29 L17.10? 2001 by Charles E. Leiserson Example of Dijkstra’s algorithm A B D C E 10 3 14 79 8 2 2 Initialize: ABCDEQ: 0 ∞∞∞∞ S: {} 0 ∞ ∞∞ ∞ Introduction to Algorithms Day 29 L17.11? 2001 by Charles E. Leiserson Example of Dijkstra’s algorithm A B D C E 10 3 14 79 8 2 2 A BCDEQ: 0 ∞∞∞∞ S: { A } 0 ∞ ∞∞ ∞ “A” ← EXTRACT-MIN(Q): Introduction to Algorithms Day 29 L17.12? 2001 by Charles E. Leiserson Example of Dijkstra’s algorithm A B D C E 10 3 14 79 8 2 2 A BCDEQ: 0 ∞∞∞∞ S: { A } 0 10 3 ∞ ∞ 10 3?? Relax all edges leaving A: Introduction to Algorithms Day 29 L17.13? 2001 by Charles E. Leiserson Example of Dijkstra’s algorithm A B D C E 10 3 14 79 8 2 2 A B C DEQ: 0 ∞∞∞∞ S: { A, C } 0 10 3 ∞ ∞ 10 3?? “C” ← EXTRACT-MIN(Q): Introduction to Algorithms Day 29 L17.14? 2001 by Charles E. Leiserson Example of Dijkstra’s algorithm A B D C E 10 3 14 79 8 2 2 A B C DEQ: 0 ∞∞∞∞ S: { A, C } 0 7 35 11 10 3?? 7115 Relax all edges leaving C: Introduction to Algorithms Day 29 L17.15? 2001 by Charles E. Leiserson Example of Dijkstra’s algorithm A B D C E 10 3 14 79 8 2 2 A B C D EQ: 0 ∞∞∞∞ S: { A, C, E } 0 7 35 11 10 3?? 7115 “E” ← EXTRACT-MIN(Q): Introduction to Algorithms Day 29 L17.16? 2001 by Charles E. Leiserson Example of Dijkstra’s algorithm A B D C E 10 3 14 79 8 2 2 A B C D EQ: 0 ∞∞∞∞ S: { A, C, E } 0 7 35 11 10 3∞∞ 7115 Relax all edges leaving E: Introduction to Algorithms Day 29 L17.17? 2001 by Charles E. Leiserson Example of Dijkstra’s algorithm A B D C E 10 3 14 79 8 2 2 ABCD EQ: 0 ∞∞∞∞ S: { A, C, E, B } 0 7 35 11 10 3∞∞ 7115 “B” ← EXTRACT-MIN(Q): Introduction to Algorithms Day 29 L17.18? 2001 by Charles E. Leiserson Example of Dijkstra’s algorithm A B D C E 10 3 14 79 8 2 2 ABCD EQ: 0 ∞∞∞∞ S: { A, C, E, B } 0 7 35 9 10 3∞∞ 7115 Relax all edges leaving B: 9 Introduction to Algorithms Day 29 L17.19? 2001 by Charles E. Leiserson Example of Dijkstra’s algorithm A B D C E 10 3 14 79 8 2 2 ABCDEQ: 0 ∞∞∞∞ S: { A, C, E, B, D } 0 7 35 9 10 3∞∞ 7115 9 “D” ← EXTRACT-MIN(Q): Introduction to Algorithms Day 29 L17.20? 2001 by Charles E. Leiserson Correctness — Part I Lemma. Initializing d[s] ← 0 and d[v] ←∞ for all v ∈ V –{s} establishes d[v] ≥δ(s, v) for all v ∈ V, and this invariant is maintained over any sequence of relaxation steps. Proof. Suppose not. Let v be the first vertex for which d[v] < δ(s, v), and let u be the vertex that caused d[v] to change: d[v] = d[u] + w(u, v). Then, d[v]< δ(s, v) supposition ≤δ(s, u) + δ(u, v) triangle inequality ≤δ(s,u) + w(u, v) sh. path ≤ specific path ≤ d[u] + w(u, v) v is first violation Contradiction. Introduction to Algorithms Day 29 L17.21? 2001 by Charles E. Leiserson Correctness — Part II Theorem. Dijkstra’s algorithm terminates with d[v] = δ(s, v) for all v ∈ V. Proof. It suffices to show that d[v] = δ(s, v) for every v ∈ V when v is added to S. Suppose u is the first vertex added to S for which d[u] ≠δ(s, u). Let y be the first vertex in V – S along a shortest path from s to u, and let x be its predecessor: s s x x y y u u S, just before adding u. Introduction to Algorithms Day 29 L17.22? 2001 by Charles E. Leiserson Correctness — Part II (continued) Since u is the first vertex violating the claimed invariant, we have d[x] = δ(s, x). Since subpaths of shortest paths are shortest paths, it follows that d[y] was set to δ(s, x) + w(x, y) = δ(s, y) when (x, y) was relaxed just after x was added to S. Consequently, we have d[y] = δ(s, y) ≤δ(s, u) ≤ d[u]. But, d[u] ≤ d[y] by our choice of u, and hence d[y] = δ(s, y) =δ(s, u) = d[u]. Contradiction. s s x x y y u u S Introduction to Algorithms Day 29 L17.23? 2001 by Charles E. Leiserson Analysis of Dijkstra degree(u) times |V | times Handshaking Lemma ?Θ(E) implicit DECREASE-KEY’s. Time = Θ(V)·T EXTRACT - MIN + Θ(E)·T DECREASE - KEY Note: Same formula as in the analysis of Prim’s minimum spanning tree algorithm. while Q ≠? do u ← EXTRACT-MIN(Q) S ← S ∪ {u} for each v ∈ Adj[u] do if d[v] > d[u] + w(u, v) then d[v] ← d[u] + w(u, v) Introduction to Algorithms Day 29 L17.24? 2001 by Charles E. Leiserson Analysis of Dijkstra (continued) Time = Θ(V)·T EXTRACT - MIN + Θ(E)·T DECREASE - KEY QT EXTRACT - MIN T DECREASE - KEY Total array O(V) O(1) O(V 2 ) binary heap O(lg V) O(lg V) O(E lg V) Fibonacci heap O(lg V) amortized O(1) amortized O(E + V lg V) worst case Introduction to Algorithms Day 29 L17.25? 2001 by Charles E. Leiserson Unweighted graphs Suppose w(u, v) = 1 for all (u, v) ∈ E. Can the code for Dijkstra be improved? while Q ≠? do u ← DEQUEUE(Q) for each v ∈ Adj[u] do if d[v] = ∞ then d[v] ← d[u] + 1 ENQUEUE(Q, v) ? Use a simple FIFO queue instead of a priority queue. ? Breadth-first search Analysis: Time = O(V + E). Introduction to Algorithms Day 29 L17.26? 2001 by Charles E. Leiserson Example of breadth-first search a a b b c c d d e e g g i i f f h h Q: Introduction to Algorithms Day 29 L17.27? 2001 by Charles E. Leiserson Example of breadth-first search a a b b c c d d e e g g i i f f h h Q: a 0 0 Introduction to Algorithms Day 29 L17.28? 2001 by Charles E. Leiserson Example of breadth-first search a a b b c c d d e e g g i i f f h h Q: a b d 0 1 1 1 1 Introduction to Algorithms Day 29 L17.29? 2001 by Charles E. Leiserson Example of breadth-first search a a b b c c d d e e g g i i f f h h Q: a b d c e 0 1 1 2 2 1 2 2 Introduction to Algorithms Day 29 L17.30? 2001 by Charles E. Leiserson Example of breadth-first search a a b b c c d d e e g g i i f f h h Q: a bdc e 0 1 1 2 2 2 2 Introduction to Algorithms Day 29 L17.31? 2001 by Charles E. Leiserson Example of breadth-first search a a b b c c d d e e g g i i f f h h Q: a bdce 0 1 1 2 2 2 Introduction to Algorithms Day 29 L17.32? 2001 by Charles E. Leiserson Example of breadth-first search a a b b c c d d e e g g i i f f h h Q: a bdceg i 0 1 1 2 2 3 3 3 3 Introduction to Algorithms Day 29 L17.33? 2001 by Charles E. Leiserson Example of breadth-first search a a b b c c d d e e g g i i f f h h Q: a bdcegi f 0 1 1 2 2 3 3 4 3 4 Introduction to Algorithms Day 29 L17.34? 2001 by Charles E. Leiserson Example of breadth-first search a a b b c c d d e e g g i i f f h h Q: a bdcegi f h 0 1 1 2 2 3 3 44 4 4 Introduction to Algorithms Day 29 L17.35? 2001 by Charles E. Leiserson Example of breadth-first search a a b b c c d d e e g g i i f f h h Q: a bdcegi fh 0 1 1 2 2 3 3 44 4 Introduction to Algorithms Day 29 L17.36? 2001 by Charles E. Leiserson Example of breadth-first search a a b b c c d d e e g g i i f f h h Q: a bdcegi fh 0 1 1 2 2 3 3 44 Introduction to Algorithms Day 29 L17.37? 2001 by Charles E. Leiserson Example of breadth-first search a a b b c c d d e e g g i i f f h h Q: a bdcegi fh 0 1 1 2 2 3 3 44 Introduction to Algorithms Day 29 L17.38? 2001 by Charles E. Leiserson Correctness of BFS Key idea: The FIFO Q in breadth-first search mimics the priority queue Q in Dijkstra. ? Invariant: v comes after u in Q implies that d[v] = d[u] or d[v] = d[u] + 1. while Q ≠? do u ← DEQUEUE(Q) for each v ∈ Adj[u] do if d[v] = ∞ then d[v] ← d[u] + 1 ENQUEUE(Q, v)