- [Instructor] Okay, now we're gonna continue
our presentation of the Ford-Fulkerson algorithm.
And just to recap a little,
in an earlier video we presented
the idea of flow in a network
and we gave a number of examples.
And we saw how to represent flows with a graph
and how to calculate the maximum flow
by iteratively finding augmenting paths in a residual graph.
So here we have the example that we worked out
in the last video,
we have the capacity graph with all of the C sub u, v.
We have the flows, these are all the F sub u, v,
and then we have the residual graph
which is the remaining capacity
after we've found augmenting paths and updated our flows.
So again, we calculate the maximum flow
by iteratively finding augmenting paths.
And to continue to recap,
we also saw that flows are subject to certain constraints.
For example, that the flow along an edge
can't exceed the edges capacity.
That's common sense.
Also common sense that apart from the source and the sink,
the flow into any given node must equal
the flow out of the node, okay?
And last we saw that the flow out of the source,
this is the source here s and the flow into the sink
these are all the edges w, t, the flow into the sink,
these are all of the edges s, u that flow out of the source,
their sums have to be the same.
So the flow out of the source
has to equal the flow into the sink.
I'm guilty, I'm guilty.
In the previous video,
I swept an important detail under the rug.
And in this video, we'll demonstrate the problem here
with this small example.
And as before, we have the capacity network
here on the left,
and all the edges labeled with all the capacities
the C sub u, v,
and here we have the initial state of our flow network.
Everything's initialized to zero.
These are all of the F sub u, v.
And here we have the residual network, which we initialize
to the capacities and the flows are zero.
So, C sub u, v minus F sub u, v
is going to be C sub u, v
because F sub u, v is zero in the initial condition.
So this is our starting point.
And let's just examine this problem for a second here.
Let's go back over here to this capacity graph.
And we can see just by looking at this small example
that the maximum flow that this capacity network here
can support is five.
We can see that.
It should be playing.
So we should have three units of flow along this edge,
one unit of flow along this edge, three units
of flow along this edge, two units of flow along this edge
and two units of flow along this edge.
So that's gonna give us a total maximum flow of five
but let me show you how we can go wrong
with this very, very small problem instance.
And it all hinges on the fact that with Ford-Fulkerson,
we don't specify how we discover our augmenting paths.
And so what if we discover this augmenting path here first?
It's perfectly reasonable that's a fine augmenting path.
We have a bottleneck of three here.
So this augmenting path can support a flow of three.
And so we're gonna update our flow.
So we have three, three, and three
and we're going to deduct three from here,
three from here and three from here.
But now we have a problem.
Look at the residual graph.
What's the problem?
The problem is that there are no more augmenting paths.
This has zero remaining capacity
so we can't even consider this route as an option.
This is the only other edge out of s
that has any remaining capacity,
it flows to b, but then from b to t, the capacity is zero
and there's no way to get over to a here.
This is a directed edge so we can't go backwards
along this edge to use this unused capacity here.
So this is what's called a blocking flow.
We've painted ourselves into a corner
by a bad choice of our augmenting paths
and we've arrived at an incorrect value
for the max flow because the algorithm would terminate here.
It sees that there are no more augmenting paths,
it would say, "Okay, I'm done."
And we'd wind up with a flow of three, three
out of the source, three into the sink and that's wrong.
That's just a wrong answer.
And I swept this detail under the rug in the previous video.
So just to prove that this does work correctly
if we have the correct,
a correct sequence of augmenting paths.
Let's just walk through it real quick.
We have three and two, we discover this one here.
So, we're going to have a flow of two along these two edges.
So we got two here, we deduct two from this edge
and deduct two from this edge,
and so now we have these remaining capacities
and then let's say the next augmenting path
that we find, from source to sink is this path here,
and so this has two, this has three
so this can support a flow of two
so we're gonna add two here and two here
and deduct two here and deduct two here
and we're gonna get this,
and then we see we have this one more augmenting path
which can support a flow of one along this one here.
And so we're going to update our flow and residual networks.
And now we found the correct maximum flow.
So there is a way to find it,
but we're not guaranteed to find it
because again Ford-Fulkerson doesn't specify how we go
and find these augmenting paths.
It just says, go out and find one.
That's a problem.
And so we need to modify the approach that we saw
in the previous video
so that we don't get stuck without recourse
when we discover an augmenting path
that yields a blocking flow.
Okay, so what are we gonna do?
The problem is by a bad sequence
of discoveries of augmenting paths,
we might discover a blocking flow
which prevents us from discovering other augmenting paths.
That's the problem.
The solution is that we're going to encode a way
of revising our flows in the residual graph.
And we're gonna do that by adding backward edges.
So where we have every single edge in the capacity graph,
we're going to have two edges in the residual graph.
One forward representing the unused capacity
and one backwards representing the flow
that we've already allocated
in addition to the forward edges.
And so in that way, we're going to encode a way
of revising our flows in the event
that otherwise would be a blocking flow.
So we're gonna use the example
that we gave in the previous video.
And in the previous video,
I showed you a sequence of discoveries
of augmenting paths that gave us the correct solution.
So remember that the correct solution is that the flow,
the maximum flow in this network is six, okay?
And we gave a good sequence of augmenting paths
in the previous video.
Now I'm gonna show you before I give you the solution,
now I'm gonna show you how we can get stuck
with this exact same example.
So here is our series of unfortunate events.
We're gonna start here.
We're gonna look for augmenting paths
in this residual network here.
And let's say we find this one first, this one here okay?
And you can see the bottleneck here is two,
so this can support a flow of two,
so we're gonna deduct two from each of these.
We're gonna add two here, here, here, and here
and we're gonna wind up with something that looks like this.
So we've added a flow of two.
Now you can see there's a flow of two
out of the source and a flow of two into the sink.
And we still have some remaining capacity here.
So we're gonna go find another augmenting path
and let's say this is the second augmenting path
that we find.
And the bottleneck here is this edge
with a capacity of one, remaining capacity of one
was the original capacity
but it's the remaining capacity here
in our residual network.
And so this augmenting path can support a flow of one.
So we're gonna add one here, one here, one here
and we're gonna deduct one from each of these edges.
So we're gonna wind up with something that looks like this.
And so now we have a flow of three.
We've got three out of the source and three into the sink.
And we know there should be three more
that we should be able to discover, all right?
So let's say this is the third augmenting path we find.
Now this has a bottleneck of one,
so this augmenting path can support a flow of one,
so we're gonna add one, one, one here.
We're gonna deduct one, one, one here
and we're gonna wind up with something like this.
And now take a look at the residual graph.
We are stuck, okay?
So this is exactly the same problem that I showed you
in the previous video, where we did find a solution.
Here we found a sequence of augmenting paths
that gets us stuck let's look.
We've got a zero along this edge
so we can't use any path that goes through a here.
We've got three here, but if we get to b,
we have these two zeros here,
there's no way to flow,
say to c or to d in order to get to t.
We've got this unused capacity here
but there's no way to use it.
So there are no more augmenting paths
in this residual network.
And we are stuck.
We really do have a problem.
So how do we fix it?
Well, like I said, for every edge
in the original capacity network,
we're gonna have two edges in our residual network.
And we're gonna have these forward edges
that match the direction of the edges
in our capacity network,
and we're gonna initialize them
with the capacity just as we did before.
But we're also gonna add for each one
we're gonna add a backward edge,
and we're gonna initialize all of those to zero.
Those are the flows here.
These are all zeros.
These are all zeros, okay?
So for every edge over here, we've got two here, one
with the original capacity and one starting at zero, okay?
This is a way of encoding flow
so that we can undo as we run our algorithm.
And that's how we're going to address the problem
of blocking flows.
Traveling backward along one of these edges amounts
to reducing the flow that we'd previously allocated.
Now, we're gonna start as before,
and we're gonna discover the same sequence
of augmenting paths that we did earlier
that got us into a problem.
And we'll see how using this approach here,
gets us out of the problem.
So we found the same augmenting path.
This is the first one that I just showed you
in the previous example.
This is exactly the same augmenting flow
or augmenting path forgive me.
And we see again that it has a bottleneck of two.
So we're gonna update two, two, two, two here.
We're gonna deduct two, two, two, two here
but we're also gonna add two to this backwards edge.
We're gonna add two to this backwards edge.
We're gonna add two to this backwards edge,
and we're gonna add two to this backwards edge
that represents the flow that we're adding here
and flow that we might decide we wanna reallocate later.
So we're gonna wind up with something that looks like this.
See, two, two, two, two, and this has been reduced to one
and then all of these that were at zero
are now at two, okay?
So we have those two updates to the residual network.
We deduct the new flow from the forward edges as before,
so that's the new available capacity,
and we add the flow to the corresponding backward edges
these dotted edges here,
and that represents the flow that we can undo if we need to.
So now we do the same thing.
We go and we hunt for another augmenting path
and we're gonna find the same one that we found
in the previous example.
This is the second path that we found this one here.
This has a capacity of one.
It can support a flow of one.
And so we're gonna add one, one, one here.
We're gonna deduct one, one, one here,
and we're gonna add one to this backward edge, add one
to this backward edge and add one to this backward edge.
Now, again, we're gonna hunt for an augmenting path
and we'll find the third path that we found
in the previous example exactly the same sequence.
This one again supports a flow of one.
The bottleneck here is this edge.
And so we're gonna add one, one, one to this flow
and we're going to deduct one to get zero,
one to get two, one to get four and we're gonna add one
to each one of these backward edges, okay?
And so we're gonna wind up with something
that looks like this.
Now this is the place where we got stuck the last time.
This is where we got stuck.
But now if we consider all the edges
in our residual network, including these backward edges,
we can find an augmenting path
through this residual network.
And that's this one here,
and notice now that we're using one of these backward edges,
and we're gonna wind up deducting the flow here two,
and reallocating it to this path here,
so we're going to be able to flow
two more units this way.
We're gonna deduct two here.
We're gonna add two here and add two here.
And so this is a way of undoing the flow
that we'd previously allocated to this edge
so that we can use our resources better.
So again, we're gonna wind up with something
that looks like this, where we've deducted two here,
we've added two here,
we've deducted two here,
we've added two here,
we've deducted two here and added two here
and this is our updated flow,
and notice that the blocking flow problem
that we had before, is now no problem at all okay?
We've found a flow of six.
That's the maximum flow.
We've got three and three out of the source.
We've got four and two into the sink,
and we have avoided this problem of a blocking flow
by using these backward edges in our residual graph.
And so we arrive at that correct maximum flow now.
Now we look at the residual graph
and even considering the backward edges,
now there really are no more augmenting paths from s to t.
And so we're done.
The algorithm terminates.
To summarize how Ford-Fulkerson works,
we initialize the flow network to all zeros.
We initialize the residual network with weights
on forward edges to correspond to the capacities.
And we initialize the weights on the backward edges to zero.
And then while augmenting paths exist in the residual graph
and that's including the forward and backward edges,
we just do the algorithm like we just did.
We update the flow network by adding the augmenting flow
to the corresponding edges.
We update the forward edges in the residual network
by deducting the augmenting flow
from the corresponding edges.
And we update the backward edges in the residual network
by adding the augmenting flow to the corresponding edge.
Now everything else I told you is true.
Is this a greedy algorithm?
Yes, it's still greedy, why?
Because even though we've added this undo feature
and coded in there your residual graph,
we still proceed by finding augmenting paths
and adding them in a greedy fashion to our solution.
So once we've added an augmenting path,
we never remove it from our solution.
So it is still a greedy algorithm.
The complexity remains the same,
and again, with Ford-Fulkerson,
we don't specify how we find augmenting paths.
We just say, find augmenting paths.
So the order has a certain arbitrariness to it.
Now I mentioned in a previous video
the Edmonds-Karp algorithm.
And Edmonds-Karp is a modification
of a Ford-Fulkerson that specifies how we find
the augmenting paths.
And if we use breadth-first search,
then this is called the Edmonds-Karp algorithm.
And the worst case complexity is a little different.
It's big O of the cardinality V times
the cardinality of E squared.
It is in large part the same algorithm as Ford-Fulkerson.
It just specifies how we discover the edges.
So what haven't we discussed?
Well, we haven't discussed reals.
Our weights could have real values.
They could be rational or irrational-valued capacities.
We've only looked at integral capacities.
And you should be aware that networks
can have real valued capacities.
We haven't given any proof of correctness
nor when we're in this class.
And we haven't talked about special applications
of network flow.
And you might be surprised to find
that we can solve bipartite matching problems.
You remember we talked about bipartite matchings
in an earlier video.
We can solve certain bipartite matching problems
by using this network flow algorithm.
And that might come as a bit of a surprise.
But if you take a CS 224,
which I recommend that's the algorithm design and analysis,
you'll see all of these things.
So that wraps up our discussion
of max flow, min cut and Ford-Fulkerson.
So in subsequent videos, we will move on
to discuss the last topic that we will cover in this class
and that's called minimum spanning trees.
That's all for now, thanks.