15-451 12/4/01 Shortest paths - Bellman-Ford, Dijkstra Global min cuts - Karger, Karger-Stein ============================================================================ Today: start by talking about a couple things we never got to in the previous lectures: algorithms for shortest paths. Then go on to neat but strange result by David Karger on algorithms for finding global min cuts in graphs (I'll define what that is when we get to it). SHORTEST PATHS ============== Given a (possibly directed) graph on n nodes with costs/lengths on edges, and one node specified as a "goal" node, find the shortest path from every node in the graph to the goal. Two standard algs: one that handles edges of negative cost but is slower and uses Dynamic Programming (Bellman-Ford), and one that is faster but requires all edges to have nonnegative weight (Dijkstra's alg). 30 30 5-------------------3-----------------4 | ^ | 10 | -20| 15 | | ^ | | | | 2-------------------1-----------------0-- 30 50 Goal Assume no negative-cost cycles (else distance not well-defined). BELLMAN-FORD algorithm. Bellman is guy who invented DP. Simple idea: start by finding shortest path (if any) that uses 0 edges. Then, inductively, say we have found shortest path from each v to goal that uses i or fewer edges. Use to find for i+1. Only have to go up to n-1. Why? PSEUDOCODE: as usual for DP, let's just compute *lengths* of the paths (rather than the paths themselves). Then later can reconstruct the paths. Will compute d[v][i] = length of shortest path from d to goal that uses i or fewer edges. initialize d[v][0] = infinity for v != goal, 0 for goal. for i=1 to n-1: for each v not equal to goal: d[v][i] = MIN(d[x][i-1] + len(vx) )) v->x If m edges and n nodes, then time is O(mn). How to recosntruct the paths? If you're at vertex v at distance d[v], move to node x such that d[v] = d[x] + len(vx). =============================================================================== Aside: this type of algorithm comes up in a lot of places. E.g., (1) Markov Decision Processes (MDPs) and Reinforcement Learning in AI. This is basically what is called "value iteration". (2) This is a lot like the O(n^2) algorithm that Klaus talked about for minimizing DFAs. One way to think about that algorithm: * suppose we only cared about inputs of length 0. Then, what would be the best partition? Answer: just split into accepting vs non-accepting states. * Now, inductively, suppose we've already computed partition consistent with inputs of length <= i, and we want to be consistent with inputs of length <= i+1? All we need to do is split blocks based on which block you get to after 1 step. =============================================================================== DIJKSTRA'S ALGORITHM -------------------- While we're at it, I don't think we ever officially described Dijkstra's algorithm. Finds shortest paths a lot like Prim's algorithm for MSTs. A lot faster than Bellman-Ford but only guaranteed to work if no negative-weight edges. Algorithm: builds tree out from goal. Instead of connecting shortest edge like in Prim, it connects edge (u,v) [u in tree, v not in tree] whose (length + distance-from-u-to-goal) is smallest. E.g., 4 10 A-----B-----C | | | 1| 2| |5 goal = A. | 2 | 4 | D-----E-----F Why does this work? The claim is that if the alg puts in (u,v), then going from v to u, and then from u to the goal in the tree, really is the shortest path from v to the goal. Proof by induction. Assume true so far. Now if there was a faster way to get from v to the goal (say this path first touches the tree so far at x) then the length is at LEAST the distance from x to the goal, plus the length of the shortest edge into x. But this is longer than the distance from u to the goal plus the length of (u,v). Done. Notice that this argument would break down if there was a negative-cost way of getting from v to x. That's why Dijkstra's algorithm doesn't allow negative-cost edges. Can anyone see an explicit example where Dijkstra would fail? To implement efficiently, can use heap to get in time O(m log n) or Fib heap to get in time O(m + n log n). =========================================================================== GLOBAL MIN CUTS --------------- The problem: Given a connected graph G, find the smallest set of edges whose removal separates the graph into at least two pieces. For instance, say this graph represents a network, and we want to know how ``robust'' it is in the sense of the the minimum number of links whose failure can cause the network to become disconnected. E.g., *---------* / | | \ * | | * \ | | / *---------* Easy fact: the minimum cut is <= the minimum degree of any node. Can anyone see how to find by solving at most n max flow problems? Just pick some s, try all possible t and compute s-t min cut. Then take the best of these. For a while, was a lot of research on how to do with fewer max-flow calculations. But then a neat result by David Karger showed you could do it by a really simple algorithm, even faster than s-t cut. One weird thing about the algorithm: It's randomized and produces a cut that may not be minimum. Actually two algorithms: Alg 1: runs in nearly-linear time, and can prove that will produce the global min cut with probability at least 1/n^2. Alg 2: way of basically doing n^2 iterations of Alg 1 without so much cost. To get 50% chance of success, need time O(n^2 log^2 n). So, if you consider the decision problem: "does the min cut have size >= k?" then this is a bit like primality testing. If you find a smaller cut then you know the answer is NO. If you run many times and never find a smaller one then you can be pretty sure the answer is YES but not 100% certain. KARGER'S MIN CUT ALGORITHM (version 1: not fastest) 1. Start with each vertex in its own component. 2. Pick a random edge out of all those that go between two different components (so now we have one fewer component). 3. When only two components left, output (the edges between) them as the cut. Can think of as: give random edge lengths and then run Kruskal's MST algorithm until only two trees left. ANALYSIS: let k = size of the min cut. -------- 1) At any point the algorithm, say an edge is ALIVE if its endpoints are still in different components. Say a cut is alive if all its edges are alive. Claim: cut is alive iff haven't picked any of its edges. Why? Why can't you kill it by somehow going "around" one of the edges? 2) We know at the start there are at least kn/2 edges. Why? Claim: at any point in time, number of ALIVE edges >= k*(#components)/2. Proof: each component must have at least k alive edges leaving it. The point of (1) and (2) is can think of the min cut as hiding out, trying not to get called on. (1) says you can only kill it by directly selecting one of its edges. (2) says there have to be a lot of edges. So, fixing some min cut C (of size k), we can directly calculate a bound on how likely it is to still be alive. Pr(C alive after 1st round) = 1 - k/(# edges) >= 1-k/(nk/2) = 1-2/n = (n-2)/n. Pr(alive after 2nd given that alive after 1st) >= 1 - k/(k(n-1)/2) = 1 - 2/(n-1) = (n-3)/(n-1). Pr(alive after 3rd given that alive after 2nd) >= 1 - 2/(n-2) = (n-4)/(n-2). So, Pr(C survives all the way to the end) >= (n-2)/n * (n-3)/(n-1) * (n-4)/(n-2) * ... * 2/4 * 1/3 = 2/(n(n-1)). That's it! Neat implication: How many minimum cuts are there? A: at most n(n-1)/2. ========Don't expect to get to below, but just FYI =========================== SPEEDING UP THE ALGORITHM [Karger-Stein] ------------------------- Idea: most likely the cut gets killed near the end. So, instead of repeating the whole process, we'd get better mileage out of just repeating the last few steps.earlier steps are less risky than later steps. Why? Q: At what point is our chance of having lost C about 50/50? Ans: when we have about n/sqrt(2) components left. By that time, our success probability is about: (n/sqrt(2))^2 / n^2 = 1/2. So, let's go down this far once, and then recursively run twice from here. Can think of this as building a binary tree (where root has degree 1) of depth 2lg(n), # leaves is n^2, where then each edge is independently destroyed with prob 1/2. Edge being destroyed corresponds to losing the minimum cut. What we want is for some path to the leaf to survive. [We proved prob of losing cut in any step given that we hadn't lost it yet was a most 1/2, so if we can prove good things for this idealized process, we will have what we want] Q: What's the probability some path to a leaf survives? (can think of the strategy of doing n^2 repititions as a root with n^2 branches leading, in depth 2lg(n), to n^2 leaves.) First, what is running time? Let's just do as a function of n. In order to make this efficient, after going partway down, lets contract components into vertices and keep multi-edges as a single edge with a weight (and then pick randomly from this weighted distribution). The point is, this allows us to view the second part as two recursive calls on a smaller graph. So, our running time is: T(n) <= O(n^2) + 2T(n/sqrt(2)) = O(n^2 log n) Now: want to show that a path survives with probability at least 1/log(n). So, we can just run our algorithm log(n) times to get constant fraction prob of success, or log^2(n) times to get high probability. Then total time is O(n^2 log^3(n)) Proof: For tree of depth d, let P_d be the probability a path survives. Looking recursively, we get: P_d = (1/2) (Prob at least one of two subtrees has path that survives) = (1/2) (2P_{d-1} - (P_{d-1})^2) (using Pr(A or B) = Pr(A) + Pr(B) - Pr(A and B)) = P_{d-1} - (1/2) (P_{d-1})^2. We can now verify that P_d >= 1/(d+1), since: 1/d - 1/(2d^2) > 1/d - 1/(d(d+1)) = 1/d One good way of looking at what we've shown is this: we have shown that we can replace n^2 independent runs of the algorithm by n^2 DEPENDENT runs of the algorithm in a way that drastically reduces running time ((n^2 * cost-of-one-run) versus (log(n) * cost-of-one-run), but only slightly reduces the chance of success (constant versus 1/log(n)).