Page 1 1 CSE 421 Algorithms Richard Anderson Lecture 10 Minimum Spanning Trees Announcements â€¢ Homework 3 is due now â€¢ Homework 4, due 10/26, available now â€¢ Reading â€“ Chapter 5 â€“ (Sections 4.8, 4.9 will not be covered in class) â€¢ Guest lecturers (10/28 â€“ 11/4) â€“ Anna Karlin â€“ Venkat Guruswami Shortest Paths â€¢ Negative Cost Edges â€“ Dijkstraâ€™s algorithm assumes positive cost edges â€“ For some applications, negative cost edges make sense â€“ Shortest path not well defined if a graph has a negative cost cycle a b c s e g f 4 2 -3 6 4 -2 3 4 6 3 7 -4 Negative Cost Edge Preview â€¢ Topological Sort can be used for solving the shortest path problem in directed acyclic graphs â€¢ Bellman-Ford algorithm finds shortest paths in a graph with negative cost edges (or reports the existence of a negative cost cycle). Dijkstraâ€™s Algorithm Implementation and Runtime S = {}; d[s] = 0; d[v] = inf for v != s While S != V Choose v in V-S with minimum d[v] Add v to S For each w in the neighborhood of v d[w] = min(d[w], d[v] + c(v, w)) s u v z y x Edge costs are assumed to be non-negative a b HEAP OPERATIONS n Extract Min m Heap Update Bottleneck Shortest Path â€¢ Define the bottleneck distance for a path to be the maximum cost edge along the path s v x u 6 5 5 3 4 2 Page 2 1 CSE 421 Algorithms Richard Anderson Lecture 10 Minimum Spanning Trees Announcements â€¢ Homework 3 is due now â€¢ Homework 4, due 10/26, available now â€¢ Reading â€“ Chapter 5 â€“ (Sections 4.8, 4.9 will not be covered in class) â€¢ Guest lecturers (10/28 â€“ 11/4) â€“ Anna Karlin â€“ Venkat Guruswami Shortest Paths â€¢ Negative Cost Edges â€“ Dijkstraâ€™s algorithm assumes positive cost edges â€“ For some applications, negative cost edges make sense â€“ Shortest path not well defined if a graph has a negative cost cycle a b c s e g f 4 2 -3 6 4 -2 3 4 6 3 7 -4 Negative Cost Edge Preview â€¢ Topological Sort can be used for solving the shortest path problem in directed acyclic graphs â€¢ Bellman-Ford algorithm finds shortest paths in a graph with negative cost edges (or reports the existence of a negative cost cycle). Dijkstraâ€™s Algorithm Implementation and Runtime S = {}; d[s] = 0; d[v] = inf for v != s While S != V Choose v in V-S with minimum d[v] Add v to S For each w in the neighborhood of v d[w] = min(d[w], d[v] + c(v, w)) s u v z y x Edge costs are assumed to be non-negative a b HEAP OPERATIONS n Extract Min m Heap Update Bottleneck Shortest Path â€¢ Define the bottleneck distance for a path to be the maximum cost edge along the path s v x u 6 5 5 3 4 2 2 Compute the bottleneck shortest paths a b c s e g f d 4 2 -3 6 6 5 4 -2 3 7 6 3 7 4 a b c s e g f d How do you adapt Dijkstraâ€™s algorithm to handle bottleneck distances â€¢ Does the correctness proof still apply? Minimum Spanning Tree a b c s e g f 9 2 13 6 4 11 5 7 20 14 t u v 15 10 1 8 12 16 22 17 3 Greedy Algorithm 1 Primâ€™s Algorithm â€¢ Extend a tree by including the cheapest out going edge a b c s e g f 9 2 13 6 4 11 5 7 20 14 t u v 15 10 1 8 12 16 22 17 3 Greedy Algorithm 2 Kruskalâ€™s Algorithm â€¢ Add the cheapest edge that joins disjoint components a b c s e g f 9 2 13 6 4 11 5 7 20 14 t u v 15 10 1 8 12 16 22 17 3 Greedy Algorithm 3 Reverse-Delete â€¢ Delete the most expensive edge that does not disconnect the graph a b c s e g f 9 2 13 6 4 11 5 7 20 14 t u v 15 10 1 8 12 16 22 17 3 Page 3 1 CSE 421 Algorithms Richard Anderson Lecture 10 Minimum Spanning Trees Announcements â€¢ Homework 3 is due now â€¢ Homework 4, due 10/26, available now â€¢ Reading â€“ Chapter 5 â€“ (Sections 4.8, 4.9 will not be covered in class) â€¢ Guest lecturers (10/28 â€“ 11/4) â€“ Anna Karlin â€“ Venkat Guruswami Shortest Paths â€¢ Negative Cost Edges â€“ Dijkstraâ€™s algorithm assumes positive cost edges â€“ For some applications, negative cost edges make sense â€“ Shortest path not well defined if a graph has a negative cost cycle a b c s e g f 4 2 -3 6 4 -2 3 4 6 3 7 -4 Negative Cost Edge Preview â€¢ Topological Sort can be used for solving the shortest path problem in directed acyclic graphs â€¢ Bellman-Ford algorithm finds shortest paths in a graph with negative cost edges (or reports the existence of a negative cost cycle). Dijkstraâ€™s Algorithm Implementation and Runtime S = {}; d[s] = 0; d[v] = inf for v != s While S != V Choose v in V-S with minimum d[v] Add v to S For each w in the neighborhood of v d[w] = min(d[w], d[v] + c(v, w)) s u v z y x Edge costs are assumed to be non-negative a b HEAP OPERATIONS n Extract Min m Heap Update Bottleneck Shortest Path â€¢ Define the bottleneck distance for a path to be the maximum cost edge along the path s v x u 6 5 5 3 4 2 2 Compute the bottleneck shortest paths a b c s e g f d 4 2 -3 6 6 5 4 -2 3 7 6 3 7 4 a b c s e g f d How do you adapt Dijkstraâ€™s algorithm to handle bottleneck distances â€¢ Does the correctness proof still apply? Minimum Spanning Tree a b c s e g f 9 2 13 6 4 11 5 7 20 14 t u v 15 10 1 8 12 16 22 17 3 Greedy Algorithm 1 Primâ€™s Algorithm â€¢ Extend a tree by including the cheapest out going edge a b c s e g f 9 2 13 6 4 11 5 7 20 14 t u v 15 10 1 8 12 16 22 17 3 Greedy Algorithm 2 Kruskalâ€™s Algorithm â€¢ Add the cheapest edge that joins disjoint components a b c s e g f 9 2 13 6 4 11 5 7 20 14 t u v 15 10 1 8 12 16 22 17 3 Greedy Algorithm 3 Reverse-Delete â€¢ Delete the most expensive edge that does not disconnect the graph a b c s e g f 9 2 13 6 4 11 5 7 20 14 t u v 15 10 1 8 12 16 22 17 3 3 Why do the greedy algorithms work? â€¢ For simplicity, assume all edge costs are distinct â€¢ Let S be a subset of V, and suppose e = (u, v) be the minimum cost edge of E, with u in S and v in V-S â€¢ e is in every minimum spanning tree Proof â€¢ Suppose T is a spanning tree that does not contain e â€¢ Add e to T, this creates a cycle â€¢ The cycle must have some edge e 1 = (u 1 , v 1 ) with u 1 in S and v 1 in V-S â€¢T 1 = T â€“ {e 1 } + {e} is a spanning tree with lower cost â€¢ Hence, T is not a minimum spanning tree Optimality Proofs â€¢ Primâ€™s Algorithm computes a MST â€¢ Kruskalâ€™s Algorithm computes a MST Reverse-Delete Algorithm â€¢ Lemma: The most expensive edge on a cycle is never in a minimum spanning tree Dealing with the assumption â€¢ Force the edge weights to be distinct â€“ Add small quantities to the weights â€“ Give a tie breaking rule for equal weight edgesRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!