Maximum Flow Problem— Ford Fulkerson Algorithm

Sethuram.S.V

4 min readMay 19, 2021

The maximum flow problem involves finding a feasible/maximum amount of flow through a single-source, single-sink flow network.

A flow network is basically a graph with a source s and a sink t. Where every vertex, except for s and t can receive and send an equal amount of flow of some stuff through it. s can only send and t can only receive stuff.

The two major algorithms used to solve this problem are — Ford Fulkerson algorithm and Dinc’s algorithm. We’re going to discuss the Ford Fulkerson algorithm, which follows a greedy approach for calculating the maximum flow in a network or graph.

Basic Terminologies

Before getting into the details about the algorithm and its working let’s get familiarized with some of the basic terminologies used along with max-flow networks and the Ford Fulkerson algorithm.

flow network — indicating the bottleneck capacity and initial flow

Augmenting path: Augmenting path can be of two types — a) non-full forward edges and b) non-empty backward edges.
Minimal cut / Bottleneck capacity: The maximum possible flow from source to sink through an augmented path.

depiction of residual flow and residual graph(on the right)

3. Residual capacity: It’s the original capacity of the edge minus the flow through the edge.

4. Residual graph: It’s a graph that indicates the additional possible flow. If there is such a path from source to sink then there is a possibility to add flow.

Note

The flow in the network should adhere to the following conditions:

For any node in the network, the input flow must be equal to the output flow, except for the source and sink.
The flow through an edge mustn't exceed its capacity.
Total flow out of the source node must be equal to the sink node.
Net flow in the edges follows skew symmetry i.e. flow(u,v) = -flow(u,v). This leads to a conclusion where you have to sum up all the flows between two nodes(either direction) to find net flow between the nodes initially.

Algorithm

Initialize the flow in all the edges to 0.
While there is an augmenting path between the source and the sink, add the path to the flow.
Update the residual graph.
Return the flow.

Algorithm — worked out

If that algorithm didn’t make much sense to you, don’t worry let’s look at an example on, “How to find the max flow?” (I haven’t drawn the residual graph at each stage, but drawing it gives a better idea while finding the flow through paths)

In the first step, we have the original graph network.
Now we head on to start finding the augmenting paths.
The first path which we take is S → A→ B→ T, where the bottleneck capacity is 5, so the flow-through path is 5.
The second path which we take is S→ C→ D→T, where the bottleneck capacity is 8, so the flow-through path is 8.
The third path which we take is S→ A→ C→ D→ B→ T, where the bottleneck capacity is 2, so the flow-through path is 2.
There are no more augmenting paths left in the network. (the current one, after assigning the flows mentioned in the above steps)
Therefore the maximum flow through the network is 5+8+2 = 15.

These augmenting paths can be taken in arbitrary order, for the same example, we could’ve taken the augmenting paths as the following:

path 1: S → C → D → B → T, flow = 7
path 2: S → C → D → T, flow = 1
path 3: S → A → B → T, flow = 5
path 4: S → A → C → D → T, flow = 2

As you can see, we end up with the same max flow of 15.

Pseudo Code

Code

Okay, let’s implement the code for the algorithm by taking the below flow network as an example.

Ford Fulkerson algorithm

The max flow for the above network is 7.

Applications

Okay now we have got the algorithm covered, so let’s look at some real-world applications. (I will be explaining the first one briefly, feel free to explore the rest on your own)

Bipartite matching: Think there are ‘m’ jobs and ’n’ job applicants. Each applicant has an interest in a certain set of jobs. Each job opening can only accept one applicant and a job applicant can be accepted by one company. Then to find a way to assign a job in such a way that as many applicants as possible can get a job. The max-flow problem can be applied here to assign a job to each student so that the maximum number of students end up with a job.
Airline scheduling
Data mining
Network reliability
Image segmentation
Distributed computing

So, we have come to the end of this post, and thank you so much 😊 if you have made it this far into this post. I will see you in my next post on some other interesting graph algorithms.

References

My Github Repository

https://github.com/Sethuram52001/DSA