To get started, we're going to look at a
general scheme for solving max-flow
min-cut problems, known as the
Ford-Fulkerson algorithm,
Dates back to the 1950s.
And the idea is to start with no flow
anywhere.
So, we initialize all edges to have
capacity zero.
And then find any path from s to t, so
that you can increase the flow along that
path.
Now, the simplest case is when the edges
all go in the same direction from source
to target.
We'll look at the other case in a minute.
In that case, so there is a path, and this
is the general algorithm that works for
any path and if there's a path from s to
t, go ahead and find it.
And if there's capacity left in each one
of the edges, if none of them were full,
then what we want to do is augment the
flow along that path.
So we put as much flow as we can through
that path.
In this case, we can put ten units of flow
through each path.
Through each edge, there's room to put
ten, and two of the edges fill up in that
case but we've increased the flow in the
network by ten in that case.
And the algorithm is just, continuing that
way, finding a path.
So here's another path.
And this one also the edges all flow from
source to target.
And in this case again, we can add ten
more units a flow cuz the last edge only
has capacity ten.
So load up those edges with that flow, and
now, we've got twenty units a flow in the
network.
Notice, when we augment along in edge,
we're preserving the vertex equilibrium,
local equilibrium at a vertex property.
We're putting some flow in and taking the
same amount of flow out.
So, here's another augmenting path.
Now, this one has what's called a backward
edge.
So notice that if, the path going from s
to t goes backwards along that edge,
And the idea is, that you can augment flow
through the whole network by removing flow
in that path.
That is, if we add five units of flow from
s to this vertex, and five units of flow
from s to this vertex, then what we can do
is remove five units of flow along this
edge.
That's to preserve the local equilibrium.
Essentially, that five units of flow gets
transferred right through.
After we remove five units and we add five
here.
That's five coming in,
There's still ten going out.
And then for the forward edges, we add the
flow.
That is, we can augment the flow along an
augmenting path, by adding flow to forward
edges and subtracting flow from backward
edges.
The maximum amount of flow that we can
push through is the remaining capacity in
forward edges and the amount of flow in
backward edges.
You can't remove more flow than is there.
In this case, we can augment the flow in
the network by five.
That, fills up the first edge.
And so now we've got 25 units of flow in
the network.
And again, the idea of removing flow from
a backward edge is very simple.
It's just a way to ensure that the local
equilibrium conditions always remains
satisfied as we're moving along the path.
In this case there's one more augmenting
path.
Okay. And that's, forward, forward,
forward, forward, backwards along that one
again and then forward, forward.
So, and then what's the maximum amount
that we can push through in this case,
this one has got five in it and it's got a
capacity of eight so we can put three more
units of flow through this network.
And we get a now we have 28 units of flow
going through the network.
And the algorithm terminates when there's
no way to find an augmenting path from s
to t.
And what's that mean?
That means that every augmenting path,
Every path from s to t contains either a
full forward edge or an empty backwards
edge.
We can't put more flow through a forward
edge and we can't remove flow from an
empty backward edge.
So when there's no more augmenting paths,
the algorithm terminates.
And so that's the algorithm.
We start with no flow.
As long as there is an augmenting path,
We, we find that path and look through the
path to find the amount, the, amount
capacit left in the most full forward edge
and the amount of flow left in the most
empty back edge.
And we increase the flow in the path by
that amount.
And if we can't find an augmenting path,
then we're done.
Now there's a few questions about this.
So that solves the maximum flow problem.
We have to look at how to compute and
min-cut.
We have to figure out a way to find an
augmenting path.
That's not to hard.
That's similar to many other graph
processing problems that we have already
solved.
And we have to, ensure that or at least
show that it always computes a max-flow.
and, there's even a question of does it
actually terminate?
Maybe you could get stuck in some kind of
situation where it removes flow on an edge
in one path and, adds it in another, and
so, even analyzing how many times it does
augmentation, is actually not so
straightforward.
So we'll take a look, at these questions.
That's the Ford-Fulkerson algorithm, the
general scheme for solving nax-flow.