Report

Algorithm Design and Analysis LECTURE 8 Greedy Graph Alg’s II • Implementing Dijkstra • MST Adam Smith 9/10/10 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Rough algorithm (Dijkstra) • Maintain a set of explored nodes S whose shortest path distance d(u) from s to u is known. • Initialize S = { s }, d(s) = 0. • Repeatedly choose unexplored node v which minimizes (v ) min e (u ,v ) : u S d (u ) ( e ) , • add v to S, and set d(v) = (v). shortest path to some u in explored part, followed by a single edge (u, v) d(u) (e) v u S s 9/10/10 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Review Question • Is Dijsktra’s algorithm correct with negative edge weights? 9/10/10 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Proof of Correctness (Greedy Stays Ahead) Invariant. For each node u S, d(u) is the length of the shortest path from s to u. x P' Proof: (by induction on |S|) s • Base case: |S| = 1 is trivial. u S • Inductive hypothesis: Assume for |S| = k 1. P y v – Let v be next node added to S, and let (u,v) be the chosen edge. – The shortest s-u path plus (u,v) is an s-v path of length (v). – Consider any s-v path P. We'll see that it's no shorter than (v). – Let (x,y) be the first edge in P that leaves S, and let P' be the subpath to x. – P + (x,y) has length · d(x)+ (x,y)· (y)· (v) 9/10/10 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Implementation •For unexplored nodes, maintain ( v ) min e ( u , v ) :u S d ( u ) ( e ). – Next node to explore = node with minimum (v). – When exploring v, for each edge e = (v,w), update ( w ) min { ( w ), ( v ) ( e )}. Priority Queue •Efficient implementation: Maintain a priority queue of unexplored nodes, prioritized by (v). 9/10/10 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Priority queues • Maintain a set of items with priorities (= “keys”) – Example: jobs to be performed • Operations: – – – – Insert Increase key Decrease key Extract-min: find and remove item with least key • Common data structure: heap – Time: O(log n) per operation 9/10/10 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Pseudocode for Dijkstra(G, ) d[s] 0 for each v V – {s} do d[v] [v] S QV ⊳ Q is a priority queue maintaining V – S, keyed on [v] while Q do u EXTRACT-MIN(Q) S S {u}; d[u] [u] explore edges for each v Adjacency-list[u] leaving v do if [v] > [u] + (u, v) then [v] d[u] + (u, v) 9/10/10 Implicit DECREASE-KEY A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Analysis of Dijkstra n times while Q do u EXTRACT-MIN(Q) S S {u} for each v Adj[u] degree(u) do if [v] > [u] + w(u, v) times then [v] [u] + w(u, v) Handshaking Lemma ·m implicit DECREASE-KEY’s. 9/10/10 PQ Operation Dijkstra Array Binary heap d-way Heap Fib heap † ExtractMin n n log n HW3 log n DecreaseKey Total m 1 n2 log n m log n HW3 m log m/n n 1 m + n log n † Individual ops are amortized bounds A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Minimum spanning tree (MST) Input: A connected undirected graph G = (V, E) with weight function w : E R. • For now, assume all edge weights are distinct. Output: A spanning tree T — a tree that connects all vertices — of minimum weight: w(T ) w(u , v ) . (u ,v )T 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Example of MST 6 12 9 5 14 8 3 9/15/2008 7 15 10 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Example of MST 6 12 9 5 14 8 3 9/15/2008 7 15 10 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Greedy Algorithms for MST •Kruskal's: Start with T = . Consider edges in ascending order of weights. Insert edge e in T unless doing so would create a cycle. •Reverse-Delete: Start with T = E. Consider edges in descending order of weights. Delete edge e from T unless doing so would disconnect T. •Prim's: Start with some root node s. Grow a tree T from s outward. At each step, add to T the cheapest edge e with exactly one endpoint in T. 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Cycles and Cuts •Cycle: Set of edges the form (a,b),(b,c),(c,d),…,(y,z),(z,a). 2 1 3 6 4 Cycle C = (1,2),(2,3),(3,4),(4,5),(5,6),(6,1) 5 8 7 •Cut: a subset of nodes S. The corresponding cutset D is the subset of edges with exactly one endpoint in S. 1 2 3 6 4 S 5 7 9/15/2008 Cut S = { 4, 5, 8 } Cutset D = (5,6), (5,7), (3,4), (3,5), (7,8) 8 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Cycle-Cut Intersection • Claim. A cycle and a cutset intersect in an even number of edges. • Proof: A cycle has to leave and enter the cut the same number of times. C S V - S 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Cut and Cycle Properties •Cut property. Let S be a subset of nodes. Let e be the min weight edge with exactly one endpoint in S. Then the MST contains e. •Cycle property. Let C be a cycle, and let f be the max weight edge in C. Then the MST does not contain f. f S e e is in the MST 9/15/2008 C f is not in the MST A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Proof of Cut Property Cut property: Let S be a subset of nodes. Let e be the min weight edge with exactly one endpoint in S. Then the MST T* contains e. f •Proof: (exchange argument) S – Suppose e does not belong to T*. e – Adding e to T* creates a cycle C in T*. T* – Edge e is both in the cycle C and in the cutset D corresponding to S there exists another edge, say f, that is in both C and D. – T' = T* { e } - { f } is also a spanning tree. – Since ce < cf, cost(T') < cost(T*). Contradiction. ▪ 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Proof of Cycle Property Cycle property: Let C be a cycle in G. Let f be the max weight edge in C. Then the MST T* does not contain f. f •Proof: (exchange argument) S – Suppose f belongs to T*. e – Deleting f from T* creates a cut S in T*. T* – Edge f is both in the cycle C and in the cutset D corresponding to S there exists another edge, say e, that is in both C and D. – T' = T* { e } - { f } is also a spanning tree. – Since ce < cf, cost(T') < cost(T*). Contradiction. ▪ 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Greedy Algorithms for MST •Kruskal's: Start with T = . Consider edges in ascending order of weights. Insert edge e in T unless doing so would create a cycle. •Reverse-Delete: Start with T = E. Consider edges in descending order of weights. Delete edge e from T unless doing so would disconnect T. •Prim's: Start with some root node s. Grow a tree T from s outward. At each step, add to T the cheapest edge e with exactly one endpoint in T. 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Prim's Algorithm: Correctness •Prim's algorithm. [Jarník 1930, Prim 1959] – Apply cut property to S. – When edge weights are distinct, every edge that is added must be in the MST – Thus, Prim’s alg. outputs the MST 9/15/2008 S A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Correctness of Kruskal • [Kruskal, 1956]: Consider edges in ascending order of weight. – Case 1: If adding e to T creates a cycle, discard e according to cycle property. e Case 1 v S e u – Case 2: Otherwise, insert e = (u, v) into T according to cut property where S = set of nodes in u's connected component. Case 2 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Review Questions Let G be a connected undirected graph with distinct edge weights. Answer true or false: • Let e be the cheapest edge in G. Some MST of G contains e? • Let e be the most expensive edge in G. No MST of G contains e? 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Non-distinct edges? 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Implementation of Prim(G,w) IDEA: Maintain V – S as a priority queue Q (as in Dijkstra). Key each vertex in Q with the weight of the leastweight edge connecting it to a vertex in S. QV key[v] for all v V key[s] 0 for some arbitrary s V while Q do u EXTRACT-MIN(Q) for each v Adjacency-list[u] do if v Q and w(u, v) < key[v] then key[v] w(u, v) ⊳ DECREASE-KEY [v] u At the end, {(v, [v])} forms the MST. 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Analysis of Prim QV Q(n) key[v] for all v V total key[s] 0 for some arbitrary s V while Q do u EXTRACT-MIN(Q) for each v Adj[u] n do if v Q and w(u, v) < key[v] times degree(u) times then key[v] w(u, v) [v] u Handshaking Lemma Q(m) implicit DECREASE-KEY’s. Time: as in Dijkstra 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Analysis of Prim n times while Q do u EXTRACT-MIN(Q) for each v Adj[u] degree(u) do if v Q and w(u, v) < key[v] times then key[v] w(u, v) [v] u Handshaking Lemma Q(m) implicit DECREASE-KEY’s. PQ Operation Prim Array Binary heap d-way Heap Fib heap † ExtractMin n n log n HW3 log n DecreaseKey Total m 1 n2 log n m log n HW3 m log m/n n 1 m + n log n † Individual ops are amortized bounds 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Greedy Algorithms for MST •Kruskal's: Start with T = . Consider edges in ascending order of weights. Insert edge e in T unless doing so would create a cycle. •Reverse-Delete: Start with T = E. Consider edges in descending order of weights. Delete edge e from T unless doing so would disconnect T. •Prim's: Start with some root node s. Grow a tree T from s outward. At each step, add to T the cheapest edge e with exactly one endpoint in T. 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Union-Find Data Structures Operation\ Implementation Array + linked-lists and sizes Balanced Trees Find (worst-case) ϴ(1) ϴ(log n) Union of sets A,B (worst-case) ϴ(min(|A|,|B|) (could be as large as ϴ(n) ϴ(log n) Amortized analysis: k unions ϴ(k log k) and k finds, starting from singletons ϴ(k log k) •With modifications, amortized time for tree structure is O(n Ack(n)), where Ack(n), the Ackerman function grows much more slowly than log n. •See KT Chapter 4.6 9/15/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne