Solving the Maximum Flow Problem, with Ford Fulkerson Method
Hey there!
Imagine you are given a task to come up with an efficient solution to produce airline schedules for thousands of routes each day. You may have to consider multiple factors like equipment usage, crew allocation, customer satisfaction, and some unpredictable weather conditions and breakdowns, etc. Don’t worry, there’s something to help you with. ;) You can think of this as a maximum-flow problem and solve it using the Ford Fulkerson method.
However, modeling this problem is really beyond the scope of this article. But this will give you a comprehensive understanding of the Ford Fulkerson method so that you can use it anywhere applicable. But before that let’s understand the maximum flow problem.
What is the maximum flow problem?
What is the greatest rate at which material can be sent (shipped) from source to the sink without violating any capacity constraints?
Given a flow network G with source s and sink t, the maximum flow problem is an optimization problem to find a flow of maximum value from s to t. Flow network G=(V, E), is essentially just a directed graph where each edge has a nonnegative flow capacity.
The Ford Fulkerson Method
The Ford Fulkerson method, also known as ‘augmenting path algorithm’ is an effective approach to solve the maximum flow problem. The Ford Fulkerson method depends on two main concepts and they are,
- Residual Network
- Augmenting paths
Now, let’s learn them first.
Residual Network
It is a graph, that has the same vertices as the original network with one or two edges for each edge in the original network. And it indicates the additional possible flow through the network. For each edge, we’ll calculate the additional flow as follows.
Additional flow = edge’s capacity — the flow of the edge
So, to create a residual network we will take our original network and will update the capacity of each edge with the additional flow corresponding to that edge. Then we will also add reverse edges to indicate the amount of flow currently going across the edges of the original network.
To make this more clear, let’s look at the following example.
In the above example, for each edge, the first value represents the flow value and the second stands for the capacity of the edge.
E.g. Let’s consider the edge C->D. Here the flow is 11 and the capacity of the edge is 14. So, if we calculate the additional flow for this edge, we get 14-11 = 3. So in the residual network, we can update the capacity of the C->D edge as 3, and then add a reverse edge with value 11 (flow value of the original network) between C and D.
Likewise, we can repeat this for all the edges, and here’s what we get as the residual network.
Augmenting path
Given a flow network G=(V, E), the augmenting path is a simple path from s to t in the corresponding residual graph of the flow network.
Ok, so far so cool?
Great! Let’s continue. Now we have the basic knowledge to understand the Ford Fulkerson method.
Ford-Fulkerson Method
(1) Initially, set the flow 'f' of every edge to 0
(2) While there exists an augmenting path 'p' in the residual network
augment the flow 'f' along 'p'
(3) return flow 'f'Let’s step through this method using the following example.
Step 1: set the flow of every edge to 0
Step 2: Now, find an augmenting path in the residual network. Here, I select the path s -> A -> D -> t. Then we have to identify the bottleneck capacity (i.e. maximum flow for that path) for the selected path. As you can see, along this path, the bottleneck capacity is 8. Now without violating the capacity constraint, update the flow values of the edges in the augmenting path. Then you will get the following flow network and the residual network.
Step 3: Then I select the augmenting path s -> C -> D -> t. Now the bottleneck capacity is 2.
Step 4: The augmenting path s -> A -> B->t, the bottleneck capacity is 2.
Step 5: augmenting path s -> C -> D -> B->t, the bottleneck capacity is 6.
Step 6: augmenting path s -> C -> D -> A-> B->t, bottleneck capacity is 1.
Look! Now there are no paths left from the s to t in the residual graph. So, there is no possibility to add flow. This means the Ford Fulkerson method is complete and we are ready to find the maximum flow.
Since the maximum flow is equal to the flow coming out of the source, in this example, the maximum flow is 10+9 = 19.
Wrapping-up
In this article, we learned the Ford Fulkerson method for finding maximum flows. There are various applications of maximum flow problem such as bipartite graphs, baseball elimination, and airline scheduling, etc. This is a very important algorithm that will boost up your competitive coding skills and also help you face your interview maybe :P
References
http://www.stanford.edu/class/cs97si/08-network-flow-problems.pdf
Introduction to Algorithms 3rd Edition by Clifford Stein, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
