What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

Read More

Ford-Fulkerson Algorithm Explained (with C++ & Java Code)

  • Sep 14, 2022
  • 7 Minutes Read
Ford-Fulkerson Algorithm Explained (with C++ & Java Code)

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:

  1. Flow specified for an edge does not exceed its capacity. 
  2. The net incoming flow should be equal to the net outgoing flow except for 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. 

graph 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. 

1. 0->1->2->5

Example 2

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

2. 0->3->4->5

example 3

Now, here you'll take 3 cars and make them reach the destination by following the path mentioned. 

Cars Reached = 2+3 = 5

3. 0->1->2->3->4->5

example 4

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:

  1. Initialize the start flow as 0.
  2. Observe the augmenting path from source to sink. 
  3. Find the max flow from that particular path.
  4. Add it to the final maximum possible flow. 

Implementation with C++ Code

Here is the C++ implementation for the Ford-Fulkerson Algorithm:

//C++ Program For Ford Fulkerson Algorithm
#include 
#include <bits/stdc++.h>

using namespace std;

int bfs(int source,int target,int n,vector<int>& parent,vector<vector<int>>& graph){
    //Update the parent vector as each node value to be -1
        fill(parent.begin(),parent.end(),-1);
    //parent of source node to be -2
        parent[source] = -2;
    //Initializing queue for storing and min capacity so far
        queue<pair<int,int>> q;
    //Source node min capacity to be 1e9
        q.push({source,1e9});
        
    //Looping while queue is not empty 
        while(!q.empty()){
            //storing top node and min capacity so far
            int u = q.front().first;
            int cap = q.front().second;
            //Removing top node from queue
            q.pop();
            //Looping all edges from u
            for(int v=0;v<n;v++){
                //finding v node has edge from u
                if(u!=v && graph[u][v]!=0 && parent[v]==-1){
                    //storing parent v to be u
                    parent[v] = u;
                    //Updating the minimum capacity
                    int min_cap = min(cap,graph[u][v]);
                    //If v is the target node then return minimum capacity
                    if(v==target){
                        return min_cap;
                    }
                    //if we didn't find target node
                    //Insert the v node and minimum capacity so far in queue
                    q.push({v,min_cap});
                }
            }
        }
    //if we didn't find path between source to target return 0
        return 0;
}

int Ford_Fulkerson(int source,int target,int n,vector<vector<int>>& graph){
    //Initializing parent vector for finding the path from source to target
    //In which we add parent of the node
        vector<int> parent(n,-1);
    //Initializing maximum flow for storing ans
        int max_flow = 0;
        int min_cap = 0;   //storing minimum capacity in each path
        
    //looping while minimum capacity become zero 
    //For finding path and minimum capacity we call function bfs()
        while(min_cap = bfs(source,target,n,parent,graph)){
            //Adding the min_cap from this path 
            max_flow += min_cap;
            //storing target node in v
            int v = target;
            
            //while we didn't find the source node
            //Looping through path stored in parent 
            while(v!=source){
                //finding parent of v node
                int u = parent[v];
                //Subtracting minimum capacity from u to v
                //And adding minimum capacity from v to u
                graph[u][v] -= min_cap;
                graph[v][u] += min_cap;
                //Update the v node to it's parent
                v=u;
            }
        }
    //Returning maximum flow in the graph
        return max_flow;
    }

void addEdge(vector<vector<int>>& graph,
             int u, int v, int w)
{
    graph[u][v] = w;
}

int main()
{
    //Intializing the graph in 2d vector
    int V = 6;
    vector<vector<int>> graph(V, vector<int> (V, 0));
  //Adding edges weight in the graph
    addEdge(graph, 0, 1, 4);
    addEdge(graph, 0, 3, 3);
    addEdge(graph, 1, 2, 4);
    addEdge(graph, 2, 3, 3);
    addEdge(graph, 2, 5, 2);
    addEdge(graph, 3, 4, 6);
    addEdge(graph, 4, 5, 6);
    
    //Printing the maximum flow from the given network Using Ford Fulkerson Method
    cout << "Maximum Flow Using Ford Fulkerson Algo: " << Ford_Fulkerson(0,5,V,graph) << endl;
    return 0;
}

 

Output:

Maximum Flow Using Ford Fulkerson Algo: 7

 

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:

ford fulkerson algorithm java example

// Ford-Fulkerson algorith in Java

import java.util.LinkedList;

class FordFulkerson {
  static final int Vertices = 6;

  // Using BFS as a searching algorithm 
  boolean bfs(int Graph[][], int source, int dest, int p[]) {
    boolean visited[] = new boolean[Vertices];
    for (int i = 0; i < Vertices; ++i)
      visited[i] = false;

    LinkedList<Integer> queue = new LinkedList<Integer>();
    queue.add(source);
    visited[source] = true;
    p[source] = -1;

    while (queue.size() != 0) {
      int u = queue.poll();

      for (int v = 0; v < Vertices; v++) {
        if (visited[v] == false && Graph[u][v] > 0) {
          queue.add(v);
          p[v] = u;
          visited[v] = true;
        }
      }
    }

    return (visited[dest] == true);
  }

  // Applying fordfulkerson algorithm
  int fordFulkerson(int graph[][], int source, int dest) {
    int u, v;
    int Graph[][] = new int[Vertices][Vertices];

    for (u = 0; u < Vertices; u++)
      for (v = 0; v < Vertices; v++)
        Graph[u][v] = graph[u][v];

    int p[] = new int[Vertices];

    int max_flow = 0;

    //Updating the residual capacities of edges
    while (bfs(Graph, source, dest, p)) {
      int path_flow = Integer.MAX_VALUE;
      for (v = dest; v != source; v = p[v]) {
        u = p[v];
        path_flow = Math.min(path_flow, Graph[u][v]);
      }

      for (v = dest; v != source; v = p[v]) {
        u = p[v];
        Graph[u][v] -= path_flow;
        Graph[v][u] += path_flow;
      }

      // Adding the path flows
      max_flow += path_flow;
    }

    return max_flow;
  }

  public static void main(String[] args) {
    int graph[][] = new int[][] { { 0, 8, 0, 0, 3, 0 }, { 0, 0, 9, 0, 0, 0 }, { 0, 0, 0, 0, 7, 2 },
        { 0, 0, 0, 0, 0, 5 }, { 0, 0, 7, 4, 0, 0 }, { 0, 0, 0, 0, 0, 0 } };
    FordFulkerson m = new FordFulkerson();

    System.out.println("Maximum Flow using Ford Fulkerson Algo: " + m.fordFulkerson(graph, 0, 5));

  }
}

 

Output:

Maximum Flow using Ford Fulkerson Algo: 6

 

Applications of Ford Fulkerson Algorithm

  1. Water Distribution Problem
  2. Circulation with Demands
  3. Bipartite Matching Problem

Time Complexity

The time taken by Ford Fulkerson Algorithm is O (max_flow * E). 

Conclusion

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. 

 

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author
Manvi Saxena
I'm Manvi Saxena, a technophile, and technical content writer. Having a curious mind helps me gain exposure and explore the latest technologies. Being a coder myself, it feels fantastic to share my knowledge via tech blogs to help others.