15-451 March 7, 2006 Breadth First Search, Shortest paths, and Minimum Spanning Trees (MST) Daniel Sleator ---------------------------------------------------- Announcements Midterm Exam Thursday, March 9. All material up to and including this lecture. Review session tomorrow in recitaiton. ---------------------------------------------------- Today's lecture: Breadth-First-Search (BFS) and shortest paths Basic generic algorithm Dijkstra's algorithm Minimum Spanning Trees Prim's algorithm Kruskal's algorithm Proofs of correctness See sections 4.4 and 4.5 of Kleinberg-Tardos -------------------------------------------- Breadth-First-Search (BFS) ------------------------- Last time we talked about DFS. An alternative way to search a graph is Breadth-First-Search. Here's pseudo-code for BFS starting from a special source vertex s. We maintain two sets of vertices Completed (C), and Frontier (F). C = {} F = {s} while (F is not empty) { F' = {} for each v in F do { for each w in adj(v) do { if (w not in C and w not in F) F' = F' union w } } C = C union F F = F' } Theorem: This algorithm eventually explores all the vertices reachable from s. An alternative implementation of this algorithm uses a queue. (Described below in the context of shortest paths.) Shortest Paths -------------- Unweighted shortest path problem: Given an undirected graph G, and a special node s (call it "the source"), find the shortest path in G from s to all other vertices. [The shortest path from s to t is the path starting at s and ending at t with the fewest edges.] We can adapt the above BFS algorithm to this problem. The algorithm is the same, except we maintain a distance field for each vertex in the graph. C = {} F = {s} d = 0 s.distance = 0 while (F is not empty) { F' = {} for each v in F do { for each w in adj(v) do { if (w not in C and w not in F) { F' = F' union w w.distance = d+1 } } } C = C union F F = F' d++ } Theorem: When the algorithm terminates the distance field of each vertex v reachable from s has been assigned the shortest path length from s to v. Proof: There's an invariant that holds at the beginning of the loop. Here it is: Invariant: The distance fields of all vertices in C and F are the shortest path distances to these vertices. These are all the vertices with distance d or less. It's easy to see that this holds initially. Let's prove it's preserved in each iteration of the loop. Consider a vertex w that's about to be added to F'. Its distance cannot be d or less, because it would have been in F or C. And there is a path from s to w of distance d+1. Therefore its shortest path distance is d+1. How do we know we've found all vertices at distance d+1? Well, any vertex at distance d+1 must have a vertex at distance d on its shortest path. And this algorithm explores all of these. [Note, we can replace w.distance = d+1 by w.distance = v.distance+1 and eliminate d from the algorithm.] Here's an alternative implementation using a FIFO queue. Q. C = {} Q = {s} s.distance = 0 while (Q is not empty) { v = Q.remove() for each w in adj(v) do { if (w not in C and not in Q) { Q.add(w) C = C union w. w.distance = v.distance+1 } } } Dijkstra's algorithm -------------------- We generalize the situation to the case where each edge has a length associated with it. So if edge e = (u,v) then let l(u,v) denote the length of this edge. Suppose that all the lengths are non-negative. Dijkstra's algorithm finds the shortest paths from a source vertex to all other vertices. Here's the algorithm as described by Kleinberg-Tardos. G is a graph (V,E), l are the lengths. (we've used d(v) instead of v.distance) (s is the source vertex) Dijkstra(G,l) For each u in V d(u) = infinity C = {s} d(s) = 0 while C != V do Select a node v not in C for which there is an edge from a node in C to v, and such that d'(v) = MIN d(u) + l(u,v) (u,v) in E u in C is as small as possible. Add v to C, and define d(v) = d'(v) After running this algorithm, the distance labels d() are the length of the shortest paths from s. (Proof below.) If we want to reconstruct these shortest paths, we can do this as follows. As each vertex v is added to C, we also remember the edge (u,v) which minimized d'(v). With this extra information, we can find our way back back from any vertex v all the way to s, via a path whose length is d(v). Call this path P_v. The following fact is the key to why the algorithm works: Lemma: At the beginning of the while loop, for any u in C, the path P_u is a shortest s-u path Proof: The proof is by induction on the size of C. Certainly it's true at the beginning, when C={s}. Now we suppose the lemma is true before we add a new vertex v to C. Let u be the vertex before v on its path. We know that u was in C before, so by induction, the path P_u was a shortest path. Could there be some other path from s to v that is shorter? Consider any such path P. That path starts in C. It must eventually leave C. Let x be the next vertex it comes to after leaving C. The length of the path from s to x must already be at least as large as d(v) --- because when we picked v we considered this option, and rejected it in favor of v. Because the edges are non-negative in length, the rest of the path P from x to v just add more to its length. Thus P cannot be shorter than the path found by the algorithm. QED. This algorithm can be efficiently implemented using a priority queue data structure. Say we have a priority queue API that supports the following operations. Each node has a distance field which is used as the priority by the queue. This makes use of a priority queue with the following API: PQ.insert(node) Insert a new node into the priority queue with priority node.distance PQ.decreasePriority(node) Assuming the given node is already in the priority queue, decrease its priority to node.distance PQ.deletemin() Delete the node of minimum key and return it. Dijkstra() { C = {} PQ = new PriorityQueue() s.inqueue = true s.distance = 0 PQ.insert(s) while (PQ is not empty) { v = PQ.deletemin() v.inqueue = false C = C union v for each w in adj(v) do { if (w not in C) { if (w.inqueue) { if ((w.distance > v.distance + l(v.w)) { w.distance = v.distance + l(v.w) PQ.decreasePriority(w) } } else { w.distance = v.distance + l(v.w) PQ.insert(w) w.inqueue = true } } } } } [Draw pictures to illustrate what this is doing] [Run through an example] Before we prove that this works, let's look at the running time. The code (excluding the priority queue operations) is like BFS. It's O(n+m). O(edges + vertices). What about the PQ operations? Well, there are at most n inserts and at most n deletemins, and there are at most m decrease keys. If all of these are O(log n) then the algorithm is O((n+m) log n) Theorem: The priority queue implementataion of Dijkstra's algorithm computes the shortest path distance from s to all other vertices. Proof: The proof is a little more complicated, because we have to talk about what the distance fields for all the nodes in the priority queue mean. Let PQ be the set of vertices in the priority queue. Here is the invariant that holds at the beginning of the while loop: Invariant: C and PQ are disjoint For all vertices in C the shortest path distance has been computed. For all vertices v in PQ the distance field is the length of the shortest path that starts from s, uses any number of vertices in C, followed by an edge from C to v. Explain why this is preserved. QED. Alternative explanation of Dijkstra's algorithm where we replace an edge of length l(u,v) by l(u,v) unit length edges. Minimum Spanning Trees ---------------------- Consider a connected undirected graph G where each edge e has a cost c(e). A spanning tree of this graph is simply a subgraph of G that is a tree and has al the vertices of G. The minimum spanning tree is simply the spanning tree of minimum total cost. Before we start, there's an important property of spanning trees that we'll make use of: Fact: Suppose we have a spanning tree t of a graph G. The operation of adding an edge to t creates a subgraph t' of G that has exactly one cycle. Now if any edge on this cycle is removed this produces a new spanning tree t' of G. Proof: Last time we showed: Theorem: an undirected connected graph is a tree if and only if it has n-1 edges. By adding an edge to a tree, it now has n edges. It's still connected, so it must have a cycle. Now deleting any edge on the cycle preserves connectivity. The new graph t' therefore must also be a tree. QED. First I'll present a very general algorithm called "The Red Rule" for computing a spanning tree, then prove that the Red Rule computes a MST. Later I'll give two algorithms for the MST problem that work by virtue of being implementations of the red rule. The Red Rule: Repeatedly color edges red according to the following criterion, until the red edges form a spanning tree. Partition the graph into two sets of vertices A and V-A such that there are no red edges between them. Pick the minimum cost edge that connects A to V-A. Color it red. Theorem: The red rule computes a MST. Proof: First of all, the Red Rule cannot create a cycle. (why?) So when there are n-1 red edges, the red edges form a spanning tree. The induction hypothesis we'll use is the following: At any point in the algorithm, there exists a minimum spanning tree T such that T contains all the red edges. Clearly this is true when we start, because there are no red edges. So any MST can be T in the Induction Hypothesis. Say the IndHyp is true at iteration i. Let's prove it for i+1. Say we have partitioned the graph into A and V-A and we're about to color an edge e=(u,v) red. By the IndHyp there's a MST T that contains all the red edges. If T contains the new edge e, then the IndHyp is preserved by coloring e red. So suppose T does not contain edge e. Here's a picture. ____________ ___________ | | e | | | .------------------. | | | | | | A | | V-A | | | | | | | | | | | | | ____________ ___________ If we add e to tree T, then this edge must form a cycle. Walk around this cycle starting from the A side of e and traversing e. Eventually this walk must take us back from V-A to A. Call this edge e'. e' cannot be colored red, because the way we chose A was that there must be no red edges from A to V-A. So modify T to produce T' by removing e from T and adding e' to it. The new tree T' is a spanning tree. Now note: C(T') = C(T) + c(e) - c(e') But by the red rule, c(c) <= c(e'), cause e was the minimum cost edge crossing the cut. Therefore C(T') <= C(T). So if T was a MST, so is T'. Thus the IndHyp is preserved with T'. QED. Prim's Algorithm ---------------- The algorithm just grows a MST from a start vertex s, by always choosing the minimum cost edge from the current tree to some vertex not in the tree. The algorithm is just like Dijkstra's algorithm with a couple of tiny tweeks. Prim() { C = {} PQ = new PriorityQueue() s.inqueue = true s.distance = 0 s.predecessor = null PQ.insert(s) while (PQ is not empty) { v = PQ.deletemin() v.inqueue = false C = C union v print "edge (v.predecessor, v) is in the MST" for each w in adj(v) do { if (w not in C) { if (w.inqueue) { if ((w.distance > l(v.w)) { w.distance = l(v.w) w.predecessor = v PQ.decreasePriority(w) } } else { w.distance = l(v.w) w.predecessor = v PQ.insert(w) w.inqueue = true } } } } } Note that we've added a predecessor field to keep track of the vertex that "caused us to be added to the PQ". The running time is the same as Dijkstra's algorithm. Correctness is simply based on the fact that it's a valid implementation of the red coloring rule. The cut in question is simply the vertices in the tree so far versus all the other vertices in the graph. Kruskal's MST algorithm ----------------------- There's a very elegant way to compute the MST using sorting and the union/find algorithm. Initialize the disjoint set data structure with the universe U of all vertices of the graph. Foreach edge e=(u,v) in increasing order of cost do { if (Find(u) != Find(v)) { Union(u,v) print (u,v) } } It's also easy to show this is an implementatin of the red rule.