. So now we've got a general scheme for computing Max Flow's Min cuts and the proof that they are equivalent. Next what we need to do is look at an analysis of the, cost of computing things to try to figure out, specific, efficient ways to compute, augmenting paths. So we already saw how to compute a Min cuts So we'll just worry about doing the Max flow. To find an augmenting path. Well there's lots of ways to find an augmenting path. any graph search is gonna work. so let's just start with BFS for example. so if word focusing terminates, that means there's no augmenting path. Does it always compute our Max slow? Yes, we showed that. and well that's if it terminates. does it always terminate? Does it oscillate back and forth? Well, it's a little more work. to show that it does always terminate. if you have to, a few other conditions. So for simplicity, we assume that each capacities are integers or there's other things that can be done with a choice of augmenting paths and maybe we'll come back to that. But to figure out how many augmenting paths there are, that's the key that requires some clever analysis. and there's been a lot of different schemes studied to try to understand a way to first find the paths cheaply and then decide to try to see how, many, how we can limit the number of augmentations. so, let's look at a, at an important special case. And it's true in lots of applications. where the edge capacities are integers, between one and some, big maximum U. and, a lot of the things that we talk about work when edge capacities are, are, are real numbers. But let's just talk about this case. so one thing to notice in that case, is that our Ford focus and method always keeps an integer value of flow We never take half a flow unit and put it through an edge. So it's always integer valued, cause the flow on each edge of the integer, capacities are integers and so everything stays to be an integer. every, every augmentation either increases or decreases by the bottleneck capacity, which is always an integer. s o, one thing that's definitely true is you only augment if you're gonna increase the flow. you have to augment. You wouldn't augment if you couldn't augment by at most one. so it's definitely true that the number of augmentations is less than or equal to the value of the flow. . So there's what's called the integrality. Integrality theorem that is important for some applications and we'll come back to it, that says if there exists an integer valued Max flow and Ford focus finds so it's and waving a little bit to talk about that but we'll work with intergers and we'll be confident that we get to the answer and so the proof of the Integraliy theorem is that it terminates in the Max flow that it finds is integer valued and that's enough. So, but, just to get an idea for what goes on, let's look at this bad case. Even when the edge capacities are integers, you could have a lot of augmenting paths. And we want to avoid this case. So look at this network here, where we have S and T. And we've got two big capacity edges coming out of S and two big capacity edges coming into T. And then we have just a little edge of capacity one going between those two intermediate vertices. here's what could happen. so, in the first generation we could decide that we wanna push flow along the path that goes across the middle. Now we're gonna look in a lot of different schemes for, finding augmenting paths, so, maybe, a scheme says, if we have a choice, let's take, as longer path as we can find. And that, so, in this case, that's what it'd do. There's another augmenting path that just goes from S to the left vortex down to P, but the algorithm, say, chooses this one So we have an algorithm that chooses this one So that increases the flow by one but then the problem is, maybe the next time, we make that middle edge a backwards edge and so now we go through and increase the flow by one along that edge and now we have a total flow of two and then maybe we alternate between these two schemes. Increment by one in the left, increment by one in the right. and it 's gonna take 200 iterations. to finally get to the Max flow. whereas a different algorithm might have gotten it done in two iterations and a hundred's not so bad, but maybe these weights are a billion or something. It would take a billion iterations. So that's bad news. Now that's too slow in algorithm. We want to try to avoid that. now there's an easy way to avoid that and that's to use the shortest path or in other ways to use the farthest path, the one you can push the most flow through. that's just an example of the kind of pitfall that you wanna avoid and try to come up with an algorithm for choosing augmenting paths in Ford Fulkerson Now the performance of the Ford Fulkerson in algorithm is gonna depend on the method used to choose the augmenting paths. here's listed four easy ways to pick augmenting paths and they're pretty easy to implement. They're very similar to Dijkstra's algorithm or Prim's algorithm and others that we've looked at. But they lead to a different number of augmenting paths, depending on the network. So for example, you could decide, let's use the shortest path. So that's just the augmenting path with the fewest number of edges. and that's just, breath for a search, essentially in the graph that ignores the full forward and empty backward edges. now it's been proven that, there's no network for which the algorithm uses more than one-half E times of E paths. so at least that's an upper bound that shows that it doesn't have this bad performance involving the capacity. I want to emphasize that this is a very conservative upper bound on the number of paths used. in an actual network it might not use anywhere near that number of augmentations. Another example is the fattest path. so that's the augmenting path, with maximum bottleneck capacity. And again, that one is pretty easy to implement. it's very similar to our implementations of Dijkstra and Prim's algorithm and we'll see in a minute. And again, it can serve of upper bound on the number of paths taken by that algorithm, is the number of e dges times the log of product of edges and capacity. but again, that's a very conservative upper bound, and in the real world it might only take a few, augmentations to computing max flow, using that method. Or you could use a random path which again is easy to implement, and randomized graph search. or depth-first search. now these conservative upper bounds are useful, but in real world networks, these algorithms are going to have running times that depend, really a lot on properties of the network. So people use diffent algorithms in different situations and the fact is that, often, we can get Max flow problems solved, even on huge networks with a relatively small number of augmenting paths.