Page 1 1 CSE 421 Algorithms g Richard Anderson Lecture 10-11 Minimum Spanning Trees 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 • Bellman-Ford algorithm finds shortest paths in a graph with negative cost edges (or reports the existence of a negative cost cycle). 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 Compute the bottleneck shortest paths a e d 4 6 6 5 4 4 a e d b c s e g f 2 -3 -2 3 7 5 3 7 b c s e g f Dijkstra’s Algorithm for Bottleneck Shortest Paths S = {}; d[s] = negative infinity; d[v] = infinity 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], max(d[v], c(v, w))) s u v z y x a b 4 1 1 1 2 2 3 3 3 4 4 5 Page 2 1 CSE 421 Algorithms g Richard Anderson Lecture 10-11 Minimum Spanning Trees 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 • Bellman-Ford algorithm finds shortest paths in a graph with negative cost edges (or reports the existence of a negative cost cycle). 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 Compute the bottleneck shortest paths a e d 4 6 6 5 4 4 a e d b c s e g f 2 -3 -2 3 7 5 3 7 b c s e g f Dijkstra’s Algorithm for Bottleneck Shortest Paths S = {}; d[s] = negative infinity; d[v] = infinity 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], max(d[v], c(v, w))) s u v z y x a b 4 1 1 1 2 2 3 3 3 4 4 5 2 Minimum Spanning Tree • Introduce Problem • Demonstrate three different greedy algorithms Pid fthtthl ith k • Provide proofs that the algorithms work Minimum Spanning Tree a e 9 6 4 14 t 15 3 b c s e g f 2 13 11 5 7 20 u v 10 1 8 12 16 22 17 Greedy Algorithms for Minimum Spanning Tree • Extend a tree by including the cheapest out going edge • Add the cheapest 4 20 b c • Add the cheapest edge that joins disjoint components • Delete the most expensive edge that does not disconnect the graph 11 5 7 20 8 22 a d e Greedy Algorithm 1 Prim’s Algorithm • Extend a tree by including the cheapest out going edge 6 15 t a 9 2 13 4 11 5 7 20 14 10 1 8 12 16 22 17 3 e c g f b s u v Construct the MST with Prim’s algorithm starting from vertex a Label the edges in order of insertion Greedy Algorithm 2 Kruskal’s Algorithm • Add the cheapest edge that joins disjoint components 6 15 t a 9 2 13 4 11 5 7 20 14 10 1 8 12 16 22 17 3 e c g f b s u v Construct the MST with Kruskal’s algorithm Label the edges in order of insertion Greedy Algorithm 3 Reverse-Delete Algorithm • Delete the most expensive edge that does not disconnect the graph 6 15 t a 9 2 13 4 11 5 7 20 14 10 1 8 12 16 22 17 3 e c g f b s u v Construct the MST with the reverse- delete algorithm Label the edges in order of removal Page 3 1 CSE 421 Algorithms g Richard Anderson Lecture 10-11 Minimum Spanning Trees 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 • Bellman-Ford algorithm finds shortest paths in a graph with negative cost edges (or reports the existence of a negative cost cycle). 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 Compute the bottleneck shortest paths a e d 4 6 6 5 4 4 a e d b c s e g f 2 -3 -2 3 7 5 3 7 b c s e g f Dijkstra’s Algorithm for Bottleneck Shortest Paths S = {}; d[s] = negative infinity; d[v] = infinity 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], max(d[v], c(v, w))) s u v z y x a b 4 1 1 1 2 2 3 3 3 4 4 5 2 Minimum Spanning Tree • Introduce Problem • Demonstrate three different greedy algorithms Pid fthtthl ith k • Provide proofs that the algorithms work Minimum Spanning Tree a e 9 6 4 14 t 15 3 b c s e g f 2 13 11 5 7 20 u v 10 1 8 12 16 22 17 Greedy Algorithms for Minimum Spanning Tree • Extend a tree by including the cheapest out going edge • Add the cheapest 4 20 b c • Add the cheapest edge that joins disjoint components • Delete the most expensive edge that does not disconnect the graph 11 5 7 20 8 22 a d e Greedy Algorithm 1 Prim’s Algorithm • Extend a tree by including the cheapest out going edge 6 15 t a 9 2 13 4 11 5 7 20 14 10 1 8 12 16 22 17 3 e c g f b s u v Construct the MST with Prim’s algorithm starting from vertex a Label the edges in order of insertion Greedy Algorithm 2 Kruskal’s Algorithm • Add the cheapest edge that joins disjoint components 6 15 t a 9 2 13 4 11 5 7 20 14 10 1 8 12 16 22 17 3 e c g f b s u v Construct the MST with Kruskal’s algorithm Label the edges in order of insertion Greedy Algorithm 3 Reverse-Delete Algorithm • Delete the most expensive edge that does not disconnect the graph 6 15 t a 9 2 13 4 11 5 7 20 14 10 1 8 12 16 22 17 3 e c g f b s u v Construct the MST with the reverse- delete algorithm Label the edges in order of removal 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) is the minimum cost edge of E with (u, v) is 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 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 of no equal weight edges • Force the edge weights to be distinct – Add small quantities to the weights – Give a tie breaking rule for equal weight edges edges Dijkstra’s Algorithm for Minimum Spanning Trees S = {}; d[s] = 0; d[v] = infinity 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], c(v, w)) s u v z y x a b 4 1 1 1 2 2 3 3 3 4 4 5 Page 4 1 CSE 421 Algorithms g Richard Anderson Lecture 10-11 Minimum Spanning Trees 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 • Bellman-Ford algorithm finds shortest paths in a graph with negative cost edges (or reports the existence of a negative cost cycle). 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 Compute the bottleneck shortest paths a e d 4 6 6 5 4 4 a e d b c s e g f 2 -3 -2 3 7 5 3 7 b c s e g f Dijkstra’s Algorithm for Bottleneck Shortest Paths S = {}; d[s] = negative infinity; d[v] = infinity 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], max(d[v], c(v, w))) s u v z y x a b 4 1 1 1 2 2 3 3 3 4 4 5 2 Minimum Spanning Tree • Introduce Problem • Demonstrate three different greedy algorithms Pid fthtthl ith k • Provide proofs that the algorithms work Minimum Spanning Tree a e 9 6 4 14 t 15 3 b c s e g f 2 13 11 5 7 20 u v 10 1 8 12 16 22 17 Greedy Algorithms for Minimum Spanning Tree • Extend a tree by including the cheapest out going edge • Add the cheapest 4 20 b c • Add the cheapest edge that joins disjoint components • Delete the most expensive edge that does not disconnect the graph 11 5 7 20 8 22 a d e Greedy Algorithm 1 Prim’s Algorithm • Extend a tree by including the cheapest out going edge 6 15 t a 9 2 13 4 11 5 7 20 14 10 1 8 12 16 22 17 3 e c g f b s u v Construct the MST with Prim’s algorithm starting from vertex a Label the edges in order of insertion Greedy Algorithm 2 Kruskal’s Algorithm • Add the cheapest edge that joins disjoint components 6 15 t a 9 2 13 4 11 5 7 20 14 10 1 8 12 16 22 17 3 e c g f b s u v Construct the MST with Kruskal’s algorithm Label the edges in order of insertion Greedy Algorithm 3 Reverse-Delete Algorithm • Delete the most expensive edge that does not disconnect the graph 6 15 t a 9 2 13 4 11 5 7 20 14 10 1 8 12 16 22 17 3 e c g f b s u v Construct the MST with the reverse- delete algorithm Label the edges in order of removal 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) is the minimum cost edge of E with (u, v) is 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 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 of no equal weight edges • Force the edge weights to be distinct – Add small quantities to the weights – Give a tie breaking rule for equal weight edges edges Dijkstra’s Algorithm for Minimum Spanning Trees S = {}; d[s] = 0; d[v] = infinity 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], c(v, w)) s u v z y x a b 4 1 1 1 2 2 3 3 3 4 4 5 4 Minimum Spanning Tree a e 9 6 4 14 t 15 3 Undirected Graph G=(V,E) with edge weights b c s e g f 2 13 11 5 7 20 u v 10 1 8 12 16 22 17 Greedy Algorithms for Minimum Spanning Tree •[Prim] Extend a tree by including the cheapest out going edge • [Kruskal] Add the cheapest edge that joins 4 20 b c cheapest edge that joins disjoint components • [ReverseDelete] Delete the most expensive edge that does not disconnect the graph 11 5 7 20 8 22 a d e Why do the greedy algorithms work? • For simplicity, assume all edge costs are distinct Edge inclusion lemma • Let S be a subset of V, and suppose e = (u, v) is the minimum cost edge of E, with u in S and v in V-S • e is in every minimum spanning tree of G • e is in every minimum spanning tree of G – Or equivalently, if e is not in T, then T is not a minimum spanning tree SV - S e 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 e is the minimum cost edge between S and V-S •T 1 = T – {e 1 } + {e} is a spanning tree with lower cost • Hence, T is not a minimum spanning tree SV - S e Optimality Proofs • Prim’s Algorithm computes a MST • Kruskal’s Algorithm computes a MST • Show that when an edge is added to the MST by Prim or Kruskal, the edge is the minimum cost edge between S and V-S for some set S. Page 5 1 CSE 421 Algorithms g Richard Anderson Lecture 10-11 Minimum Spanning Trees 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 • Bellman-Ford algorithm finds shortest paths in a graph with negative cost edges (or reports the existence of a negative cost cycle). 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 Compute the bottleneck shortest paths a e d 4 6 6 5 4 4 a e d b c s e g f 2 -3 -2 3 7 5 3 7 b c s e g f Dijkstra’s Algorithm for Bottleneck Shortest Paths S = {}; d[s] = negative infinity; d[v] = infinity 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], max(d[v], c(v, w))) s u v z y x a b 4 1 1 1 2 2 3 3 3 4 4 5 2 Minimum Spanning Tree • Introduce Problem • Demonstrate three different greedy algorithms Pid fthtthl ith k • Provide proofs that the algorithms work Minimum Spanning Tree a e 9 6 4 14 t 15 3 b c s e g f 2 13 11 5 7 20 u v 10 1 8 12 16 22 17 Greedy Algorithms for Minimum Spanning Tree • Extend a tree by including the cheapest out going edge • Add the cheapest 4 20 b c • Add the cheapest edge that joins disjoint components • Delete the most expensive edge that does not disconnect the graph 11 5 7 20 8 22 a d e Greedy Algorithm 1 Prim’s Algorithm • Extend a tree by including the cheapest out going edge 6 15 t a 9 2 13 4 11 5 7 20 14 10 1 8 12 16 22 17 3 e c g f b s u v Construct the MST with Prim’s algorithm starting from vertex a Label the edges in order of insertion Greedy Algorithm 2 Kruskal’s Algorithm • Add the cheapest edge that joins disjoint components 6 15 t a 9 2 13 4 11 5 7 20 14 10 1 8 12 16 22 17 3 e c g f b s u v Construct the MST with Kruskal’s algorithm Label the edges in order of insertion Greedy Algorithm 3 Reverse-Delete Algorithm • Delete the most expensive edge that does not disconnect the graph 6 15 t a 9 2 13 4 11 5 7 20 14 10 1 8 12 16 22 17 3 e c g f b s u v Construct the MST with the reverse- delete algorithm Label the edges in order of removal 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) is the minimum cost edge of E with (u, v) is 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 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 of no equal weight edges • Force the edge weights to be distinct – Add small quantities to the weights – Give a tie breaking rule for equal weight edges edges Dijkstra’s Algorithm for Minimum Spanning Trees S = {}; d[s] = 0; d[v] = infinity 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], c(v, w)) s u v z y x a b 4 1 1 1 2 2 3 3 3 4 4 5 4 Minimum Spanning Tree a e 9 6 4 14 t 15 3 Undirected Graph G=(V,E) with edge weights b c s e g f 2 13 11 5 7 20 u v 10 1 8 12 16 22 17 Greedy Algorithms for Minimum Spanning Tree •[Prim] Extend a tree by including the cheapest out going edge • [Kruskal] Add the cheapest edge that joins 4 20 b c cheapest edge that joins disjoint components • [ReverseDelete] Delete the most expensive edge that does not disconnect the graph 11 5 7 20 8 22 a d e Why do the greedy algorithms work? • For simplicity, assume all edge costs are distinct Edge inclusion lemma • Let S be a subset of V, and suppose e = (u, v) is the minimum cost edge of E, with u in S and v in V-S • e is in every minimum spanning tree of G • e is in every minimum spanning tree of G – Or equivalently, if e is not in T, then T is not a minimum spanning tree SV - S e 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 e is the minimum cost edge between S and V-S •T 1 = T – {e 1 } + {e} is a spanning tree with lower cost • Hence, T is not a minimum spanning tree SV - S e Optimality Proofs • Prim’s Algorithm computes a MST • Kruskal’s Algorithm computes a MST • Show that when an edge is added to the MST by Prim or Kruskal, the edge is the minimum cost edge between S and V-S for some set S. 5 Prim’s Algorithm S = { }; T = { }; while S != V choose the minimum cost edge () ith i S d i V S e = (u,v), with u in S, and v in V-S add e to T add v to S Prove Prim’s algorithm computes an MST • Show an edge e is in the MST when it is added to T Kruskal’s Algorithm Let C = {{v 1 }, {v 2 }, . . ., {v n }}; T = { } while |C| > 1 Let e = (u, v) with u in C i and v in C j be the j minimum cost edge joining distinct sets in C Replace C i and C j by C i U C j Add e to T Prove Kruskal’s algorithm computes an MST • Show an edge e is in the MST when it is added to T Reverse-Delete Algorithm • Lemma: The most expensive edge on a cycle is never in a minimum spanning tree Dealing with the assumption of no equal weight edges • Force the edge weights to be distinct – Add small quantities to the weights – Give a tie breaking rule for equal weight edges edgesRead More

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