In this video, I'll talk about how to solve the maximum flow problem in a network using
the Ford-Fulkerson method.
In the first step of the Ford-Fulkerson method, we need to check if there still exists a path
from the source to the sink.
If there is a path from the source to the sink, go to Step 2.
Otherwise, the optimal solution is determined by the backward arcs.
In step 2, we need to create a residual flow network using the following substeps.
Find the smallest capacity of the arcs on the path.
Denote it by c.
Subtract c from the capacity of each arc on the path.
Add a backward arc for each arc on the path.
Add c to the capacity of each reverse arc.
Finally, go back to Step 1 and check if the optimal solution is found.
Let's check this example.
Suppose a water treatment plant wants to pump the maximum amount of water through pipelines
from source node S to sink node T.
The water supply network is shown here.
For example, from node S to node A, the capacity is 6 million gallons of water per day; from
node A to node B, the capacity is 2 million gallons per day, and so on.
In the first step, let's find a path from S to T. There are several paths.
We only need to identify one path at this time.
For example, this path S-A-B-T.
Now, in step 2, we need to find the smallest capacity of the arcs on this path.
Denote it by c.
So c=2.
Subtract 2 from the capacity of each arc on the path.
This will be changed to 4, this will be 0 and we can remove it from the network, and
this will be changed to 1.
Now, we add a backward arc for each arc on that path.
Add 2 to the capacity of each reverse arc.
This will be 2, this will be 2, and this will be 2.
So, this is a residual flow network.
Let's go back to Step 1 and check if there is still a path from S to T.
Yes, there is a path, S-C-D-T.
We need to find the smallest capacity of the arcs on this path.
Denote it by c.
So c=5.
Subtract 5 from the capacity of each arc on the path.
This will be 0 and we can remove it from the network, this will be changed to 2, and this
will be changed to 3.
Now, we add a backward arc for each arc on that path.
Add 5 to the capacity of each reverse arc.
This will be 5, this will be 5, and this will be 5.
So, this is a residual flow network.
Let's go back to Step 1 and check if there is still a path from S to T.
Yes, there is a path, S-A-D-T.
We need to find the smallest capacity of the arcs on this path.
Denote it by c.
So c=3.
Subtract 3 from the capacity of each arc on the path.
This will be changed to 1, this will be changed to 1, and this will be 0 and we can remove
it from the network.
Now, we add a backward arc for each arc on that path.
Add 3 to the capacity of each reverse arc.
There is already a reverse arc from A to S and its old capacity is 2.
So 2+3=5.
There is no reverse arc between D and A, so we add a reverse arc and the capacity is 3.
There is already a reverse arc from T to D and its old capacity is 5.
So 5+3=8.
So, this is a residual flow network.
Let's go back to Step 1 and check if there is still a path from S to T.
We can no longer find a path from S to T. So, the optimal solution is determined by
the backward arcs.
Let's remove the original forward arcs and only keep the backward arcs.
This is the optimal solution.
That means, we should pump 5 million gallons of water from S to A, 2 million gallons from
A to B, and so on.
The maximum flow is 5+5 or 2+8, which is equal to 10 million gallons.
Okay, that is how to solve the maximum flow problem in a network using the Ford-Fulkerson
method.
Thanks for watching.