RECITATION NOTES 15-451 Algorithms 10/08/03 * Topological sorting * Shortest paths - Dijkstra (review from 15-211) - Bellman-Ford ========================================================================== TOPOLOGICAL SORTING. A "DAG" or directed-acyclic-graph is a directed graph without any cycles. E.g., A----->D--->E |\ ^ | \ | | \ | | | / V V/ C<--B<----F Given a DAG, the "topological sorting" problem is: find an ordering of the vertices such that all edges go forward in the ordering. Typically comes up when given a set of tasks to do with precedence constraints (need to do A and F before you can do B), and want to find a legal ordering of performing the jobs. How can we solve this problem? Here is a method you might come up with: 1. find a node v with no in-edges and output it. 2. remove v and its outedges 3. goto 1. Step 1 takes O(n) time, so overall this takes O(n^2) time. Can improve this using a heap data structure to store in-degree [when we remove v, we do decrease-key on its neighbors]. This costs O(log m) for each outedge removed in step 2, so O(m log m) overall. [n = number of vertices. m = number of edges]. But here's a neat linear-time algorithm based on depth-first search: How to solve Topological Sorting #2: 1. Do depth-first search of G, and output the nodes as you *exit* them. 2. reverse the order. To be specific, by "DFS of G" we mean "pick a node and do DFS from there. If the whole graph hasn't been visited, then pick an unvisited node and repeat the process. Continue until everything is visited". E.g., DFS-main(G): For v=1 to n: if v is not yet visited, do DFS(v). DFS(v): mark v as pre-visited. for each unmarked neighbor w of v: do DFS(w). postvisit(v). // <-- output here! Claim: If there is an edge from u to v, then v is exited first. (This implies that when we reverse the order, we have a topological sorting.) Proof of claim: [Think of u=B, v=D above.] Easy to see if our DFS started at u before starting at v. What if we started at v first? In this case, we would finish v before even starting u since there can't be a path from v to u (else wouldn't be acyclic). Note: can use same alg to tell if graph has any cycles. ======================================================================= Shortest paths ============== Suppose we are given a graph G and a start node S, and we want to find the shortest path from S to everywhere in G. (called the "shortest path tree" from S). In 15-211, you saw Dijkstra's algorithm for this problem. Idea is to build up shortest-path tree in greedy way. Today: review Dijkstra and also show a different DP-based algorithm called the "Bellman-Ford" algorithm. Bellman is the guy who invented Dynamic Programming. E.g., 5 8 A-----B-----C | | | 1| 1| |6 start = A. | 2 | 4 | D-----E-----F DIJKSTRA's ALG -------------- initialize: - tree = {start}. No edges. label start as having distance 0. invariant: nodes in tree have correct distance to start. repeat: - for each nbr x of tree compute an (over)-estimate of distance to start: distance(x) = min [ distance(v) + length(e) ] edges e=(v,x) v in tree In other words, by our invariant, this is the length of the shortest path to x whose only edge not in the tree is the very last edge. - put x of minimum distance into tree, connecting it via the argmin (the edge that caused the distance to be what it is) [do above example] Claim: even if some of distances are wrong, the *minimum* one is correct. Proof: say x is node of smallest distance(x). What does the *true* shortest path to x look like? The point is that the last edge this path takes must come directly from the tree, since any other path would have length at least y.dist from some y!=x, and by definition, distance(x) is smaller. Running time: if you use a heap and code this up right, you can get time of O(m log n). If you use something called a "fibonacci heap" (that we're not going to talk about) can get time down to O(m + n log n) What if some of the edge costs are negative? (For this to make sense, we need to assume the graph is *directed*, and there are no negative-cost cycles. Otherwise you can have a distance of negative-infinity by going around such a cycle infinitely-many times...) Will Dijkstra's algorithm still work? NO. Can anyone give an example?? It turns out these kinds of problems do come up --- in fact, we will need to solve this problem as a subroutine (shortest paths when some edge costs are negative) in some later algorithms in this course. So, here is a different algorithm that works in that case. The BELLMAN-FORD Algorithm ========================== 30 15 Say we have a graph 5-------------------3-----------------4 like this: | ^ | 10 | -40| 40 | | | | | | | 2-------------------1-----------------0-- 30 60 start Will use DP to solve the shortest-path problem. Alg idea: find shortest path that uses 1 or fewer edges (if it exists) use to find shortest path that uses 2 or fewer edges (if it exists). use to find shortest path that uses 3 or fewer edges (if it exists). ... [how far do we need to go?] use to find shortest path that uses n-1 or fewer edges. BELLMAN-FORD pseudocode: as usual for DP, let's just compute *distances* first, and then can reconstruct the paths. d[v][i] will mean the length of the shortest path to v that uses i or fewer edges (if it exists). initialize d[v][0] = infinity for v != start, 0 for start. for i=1 to |V|-1: for each v not equal to start: d[v][i] = MIN(d[x][i-1] + len(xv) )) x->v (try it on the above graph!) Inner MIN operation takes time proportional to in-degree of v. So, inner for-loop takes time O(sum of out-degrees of all nodes) = O(m). --> total time is O(mn). How to recosntruct the paths? Work backwards: if you're at vertex v at distance d[v], move to node x such that d[v] = d[x] + len(xv). ===============================================================================