. 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.