As everybody is leaning toward a more technological-dependent world, programming has become one of the major skills to possess. Around 26.8 million software developers and programmers are active in this world. With such a huge number of people working towards technological development, complex problems are bound to come up. Thus, experts all over the world are continuously devising specific algorithms to tackle particular types of questions.
One such algorithm is Ford Fulkerson Algorithm. It is a sort of greedy approach that we follow to find a solution to the Max-Flow Min-Cut Problem. Discovered in 1956 by Ford and Fulkerson, this algorithm tackles the above-stated problem in a very neat way. In this blog, we shall discuss all these problems, the algorithm to solve them, and its implementation in 2 languages- C++ & Java.
What is Ford-Fulkerson Algorithm?
Ford-Fulkerson Algorithm is a set of steps that we follow to tackle the max-flow min-cut problem. It uses a greedy approach to find the maximum flow coming out of a flow network.
Don't know what the max-flow min-cut problem is? Don't worry, let's start from the beginning.
What is Max-Flow Min-Cut Problem?
You are given a graph that represents a network flow as illustrated in the given image. Every edge of this network has a certain capacity. You are also given 2 special vertices called source 's' and sink 't'. Now, you need to find the maximum possible flow from source to sink with the following constraints:
- Flow specified for an edge does not exceed its capacity.
- The net incoming flow should be equal to the net outgoing flow except for s and t.
To understand the intuition behind this, first, let's go through some terminologies that we'll be using throughout.
Terminologies used in the Problem
Augmenting Path: The multiple paths available in the flow network.
Residual Graph: The flow network that has additional flow.
- Residual Capacity: The capacity of flow left in the edge after subtracting the flow.
Understanding the Ford-Fulkerson Approach with an Example
The intuition behind solving this problem is quite simple. Let's understand this with help of an example.
Imagine you have a network of roads from where daily certain cars travel. Take a look at below car network. Now, obviously, the roads cannot be infinitely wide, thus, they all have a fixed width that ensures only a certain number of cars travel through them at a time. There is a starting point and a destination as well. The cars always start from the starting point and have to reach the destination. But, there are several paths to take. Let's start sending cars one by one to all the roads.
Here, you'll start by sending 2 cars for 0->1. Why? Although this road's capacity is 4 if we look further, only 2 cars can pass through 2->5. Therefore, we take 2 here. Now, 2 cars have reached their destination.
Cars Reached = 2
Now, here you'll take 3 cars and make them reach the destination by following the path mentioned.
Cars Reached = 2+3 = 5
Now, 2 cars have already gone through road 0->1 and 1->2, therefore, we'll take the remaining cars, that is, 2. Similarly, on road 2->3 we have a residual capacity of 3 so, after traveling of 2 cars, we'll have 1 over there. The same goes for the other 2 roads in this augmenting path.
Cars Reached = 5+2 = 7
Now, although we still have paths left, we don't have any augmented paths. Why? This is because, the path starting from the source has ended, the roads have been full to their capacity and thus, we cannot make any more cars travel.
Therefore, the final answer comes out to be 7. In the same way, we process the maximum flow by taking cars as data or any other element.
Steps to Follow
Now that you've understood what to do, it's important that you know how to do it. Below are the steps to be followed to find the maximum flow in a network:
- Initialize the start flow as 0.
- Observe the augmenting path from source to sink.
- Find the max flow from that particular path.
- Add it to the final maximum possible flow.
Implementation with C++ Code
Here is the C++ implementation for the Ford-Fulkerson Algorithm:
Let's take another flow network and find the maximum possible flow using its implementation in Java.
Implementation with Java Code
The graph we used over here is:
Applications of Ford Fulkerson Algorithm
- Water Distribution Problem
- Circulation with Demands
- Bipartite Matching Problem
The time taken by Ford Fulkerson Algorithm is O (max_flow * E).
The Ford Fulkerson Algorithm is an essential topic to enhance your programming skills. While solving it a high sense of imagination power is definitely required to search for all the potential augmenting paths and find out the residual capacity of the same. In this tech blog, we understood the whole algorithm step by step in a comprehensive manner and later, implemented it using the codes.