Hello everybody and welcome back to our Network Flows Unit. Today we're going to be talking a new algorithm for network flows, or maybe just a version of the old algorithm, that will do a little bit better than what we had previously. So last time, we were still talking with the Ford-Fulkerson algorithm for Maxflow. The runtime, in general, is O of the number of edges times the size of the flow. And last time we showed that this can actually be very very slow on graphs with large capacities. And in particular, we had this example, where sort of every time, if you routed flow, at least if you were picking the wrong paths, then you just got one unit of flow every iteration and it took millions of iterations to actually finish. Fortunately though, we know that the Ford-Fulkerson algorithm gives us a choice as to which augmenting path to use. And the hope is that maybe by picking the right path we can guarantee that our algorithms won't take that long. And so in particular what we want to do is we want to find sort of a principled way of picking these augmenting paths in order to ensure that our algorithm doesn't run through too many iterations. And one way to do this is via what's known as the Edmonds-Karp algorithm. The idea of the Edmonds-Karp algorithm is as follows. We'd like to use the Ford-Fulkerson algorithm but we're always going to be using the shortest possible augmented path. That is, shortest in the number of edges that are being used. And, basically all that this means is that if we want to find our augmenting paths, we want to use a breadth-first search, rather than a depth-first search. So, for example, if we're trying to run Edmonds-Karp on this example, then we can't use the zig-zag path with three edges. We're required to pick this augmenting path with only two edges instead. After we've done that there's another path with only two edges, and after we've done that there's nothing left to be done. So at least on this example the Edmonds-Karp algorithm gives us the good execution rather than the bad one. Now to really look into how well this works, we need to analyze these augmenting paths. So if you have an S to T path. You'll note that when you add your augmenting flow it always saturates some edge. That is, uses up all the available flow from that edge. And this is because the way we decided the amount of flow to run along this path was we took the minimum capacity of any of these edges in the residual graph. And so which ever edge had only that much capacity left got saturated. Now, once we add this augmenting flow, we have to modify the residual network. We end up with edges pointing backwards along each of these places because we can now cancel out that flow we just added. And, at least the one edge that we ended up saturating, we destroyed that edge, we used up all of the remaining flow. Okay, so we'd like to now analyze the Edmonds-Karp algorithm. And the basic idea is that whenever we have an augmenting path, we always saturate some edge. And we're going to show that we don't have too many different augmenting paths by showing that no edge is saturated too many times. Now we'll note this really fails to hold in the bad case that we looked at because the middle edge kept on being saturated over and over again, it just flipped from going pointing up to pointing down in the residual graph over and over again. And this was the real thing that was limiting to us to adding one unit of flow per iteration. Okay. So that's the idea of our analysis and the way we're going to show that this works is we're going to start with a critical lemma. The Edmonds-Karp algorithm is very concerned about distances in the residual graph because it looks for short paths there. And so we'd like to know how these distances change as the algorithm executes. Because as you run your algorithm your residual graph keeps changing, and so the distances inside the residual graph change. Now the Lemma that we want is the following. As the Edmonds-Karp algorithm executes, if you take any vertex v and look at the distances from the source to v, those distances only get bigger. Similarly look at the distances from from v to t or the distance from s to t, again those can only increase, never decrease. And the proof is not so bad but it's a little subtle. So, whenever we have an augmenting path, we introduce a bunch of new edges that point backwards along this augmenting path. Now the augmenting path sort of by assumption was always the shortest path from source to sink. And what that means is that the new edges point from vertices that were further away from s to vertices that are closer to s. And the key observation is that new vertices of that form never give you any faster paths from source to v. And this is because, well if I told you someone introduced a great, fast, one-way highway that went from a city 1,000 miles away from your house to a city 10 miles away from your house, it would not actually be useful for you to get anywhere from home. Now it would be incredibly useful getting back from this other place, but if you wanted to get to this place 10 miles away, you could just drive 10 miles instead of driving 1,000 miles and taking the new highway. Similarly these edges that only point from distances farther from S to vertices closer to S, they never help you get to places from S any faster than you were before. Now the saturated edges that got removed might make things become slightly further away than they were before, but the new edges never make anything closer. And that basically completes our proof. The fact that distances at vertices to T increase is completely analogous, as is the proof that vertices from S to T increase. So, with that under our belts, the critical lemma now is the following. We want to show that there's a limit on how often edges can be resaturated. And so we have the following lemma. When running the Edmonds-Karp algorithm, if an edge e is saturated, that edge cannot be used again in any augmenting path at least until the distance between s and t and the residual graph has increased. Now the proof this is a little bit subtle, so we're going to first consider this path that caused us to saturate the edge. So the path went from s to u, this had length x, then from u to v which was our edge. And then from v to t which had length y. Now, this had to be a shortest path. And so the path from s to t had to be x+y+1. Now, when we use that edge again, we use this edge from v back to u. Well, we need to have some path from s going to v then to u and then from u to t. Now this has to be the shortest path. Now what's the distance from s to v? The distance from s to v is at least what the distance from s to v was before, which was x + 1. Then the distance from v to u is one and the distance from u to t is at least what it was before, which is at least y + 1. So that means when this edge gets used again, the distance from s to t had be at least (x + 1) + (y +1) + 1, which is at least x + y + 3. Which means that when this edge gets used again, it has to be the case that the distance between s and t was bigger than it was before. And that completes our proof. Once we have this lemma the rest of this analysis is actually pretty easy. The distance between s and t in the residual graph can only increase and it's never more than the number of vertices. So it can only increase the number of vertices times. Now between times that it increases, no edge can be saturated more than once because once it's saturated you can never use it again. And so between times you can only have O of E many saturated edges. But each augmenting path has to saturate an edge. You can only have O of E many such paths between increases in this distance between s and t. And that can happen only O of E many times. So there are only O of size of V times size of E many augmenting paths used by this algorithm. Each path here takes only O of E much time. And so the total run time, is at most, O of V times E squared. Now, this is maybe not so great, because, O of E times E squared, this might be number of vertices to the fifth, or number edges cubed. But it is polynomial and it has no dependence on, or it sort of doesn't become very, very, very big when our actual size of our flow becomes very, very large. Okay. So one problem, sort of a quick review properties of this Edmonds-Karp algorithm. Which of the following are true about the Edmonds-Karp algorithm? One, that no edge is saturated more than size of V many times. Two, the lengths of the augmenting paths decrease as the algorithm progresses. Or three, that changing the capacities of edges will not affect the final runtime. Well, it turns out that only one of these is true. Yes, edges only become resaturated after the distance between S and T increases, which only happens V many times. However, the lengths of the augmenting paths increase as the algorithm progresses, not decrease. And finally, although the runtime does not have an explicit dependence on the edge capacities, like it did in the Ford-Fulkerson algorithm, they can still affect the runtime. If all the capacities are zero, you don't need to do any augmenting paths. If the capacities are weird, they might make you do a little bit more work than you'd have to do otherwise. But the nice thing about Edmonds-Karp is that there's a bound to how bad it can be. So in summary if we choose augmenting paths based on length it removes this sort of, at least bad dependence that we had on the numerical sizes of the capacities. We have a runtime we can write down that we can run independently of our total flow. And now max flow is an incredibly well studied algorithmic problem. There are actually better more complicated algorithms that we're just not going to get into in this course. The state of the art is a little better than what we had, it's O of number of vertices times number of edges. And if you want to look it up, I mean, feel free to look up these more complicated algorithms. But this is all that we're going to do in this course. The next two lectures, we're going to sort of talk about some applications of these maxflow algorithms to a couple other problems where it's not quite obvious that this is the right thing to do. So I'll see you next time.