Ford Fulkerson Algorithm for Maximum flow in a graph


Reading time: 15 minutes | Coding time: 9 minutes

Ford–Fulkerson algorithm is a greedy algorithm that computes the maximum flow in a flow network. The main idea is to find valid flow paths until there is none left, and add them up. It uses Depth First Search as a sub-routine.

Pseudocode


* Set flow_total = 0
* Repeat until there is no path from s to t:
   * Run Depth First Search from source vertex s to find a flow path to end vertex t
   * Let f be the minimum capacity value on the path
   * Add f to flow_total
* For each edge u → v on the path:
   * Decrease capacity of the edge c(u → v) by f
   * Increase capacity of the edge c(v → u) by f

Before moving forward, think about the following questions:

  1. What is the worst case scenario for Ford Fulkerson algorithm?

  2. Will Ford Fulkerson algorithm terminate for all graphs?


Worst case scenario:

Flow increments by 1 in each step for a graph such as:

Worst case scenario

It takes 2000 steps to find the maximum flow in the above graph. If we used Breadth First Search instead of Depth First Search in Ford Fulkerson algorithm, it will take 2 steps.

Non-terminating example:

Ford Fulkerson algorithm will not terminate for the following graph:

Non-terminating example

How do we know if this gives a maximum flow?

Proof overview:

We will use proof by contradiction.

Suppose Ford–Fulkerson algorithm will not give the maximum flow.

Take a maximum flow f and “subtract” our flow f. It is a valid flow of positive total flow. By the flow decomposition, it can be decomposed into flow paths and circulations. These flow paths must have been found by Ford-Fulkerson.

This leds to a contradiction. Hence, Ford–Fulkerson algorithm will give the maximum flow.

Complexity

  • Worst case time complexity: Θ(max_flow * E)
  • Average case time complexity: Θ(max_flow * E)
  • Best case time complexity: Θ(max_flow * E)
  • Space complexity: Θ(E + V)

Implementations

  • C++
  • Java
  • Python

C++


/* Part of Cosmos by OpenGenus Foundation */
#include <iostream>
#include <string.h>
using namespace std;
#define N 7
#define INF 9999999
// flow network
int Flow[N][N];
// visited array
bool visited[N];
// original flow network graph shown in the above example
//0 1  2  3  4 5  6
int graph[N][N] = {
        { 0, 5, 4, 0, 0, 0, 0 }, //0
        { 0, 0, 0, 0, 0, 0, 4 }, //1
        { 0, 0, 0, 3, 0, 0, 6 }, //2
        { 0, 0, 0, 0, 5, 0, 0 }, //3
        { 0, 0, 0, 0, 0, 0, 8 }, //4
        { 6, 0, 0, 2, 0, 0, 0 }, //5
        { 0, 0, 0, 0, 0, 0, 0 }, //6
        };
int dfs(int s, int t, int minimum) {
    visited[s] = true;
    // if source and sink is same
    if (s == t)
        return minimum;
    for (int i = 0; i < N; i++) {
        int flow_capacity = graph[s][i] - Flow[s][i];
        if (!visited[i] && flow_capacity > 0) {
            // find min capacity in dfs path
            if (int sent = dfs (i, t, min (minimum, flow_capacity))) {
                // adjust the capacity
                Flow[s][i] += sent;
                Flow[i][s] -= sent;
                return sent;
            }
        }
    }
    return false;
}
int main() {
    // initialize initial flow capacity 0
    memset(Flow, 0, sizeof(Flow));
    // initialize visited array false initially
    memset(visited, 0, sizeof(visited));
    int s = 5;
    int t = 6;
    int max_flow = 0;
    // while ther is augmenting path , from s and t
    // with positive flow capacity
    while (int sent = dfs(s, t, INF)) {
        max_flow += sent;
        // reset visited array , for searching next path
        memset(visited, 0, sizeof(visited));
    }
    cout << "The max flow from node 5 to sink node 6 is " << max_flow;
    cout << endl;
}

Java


// Part of Cosmos by OpenGenus Foundation
import java.util.LinkedList;
import java.lang.Exception;
class FordFulkersonUsingBfs {
	static final int V = 6;
	boolean bfs(int rGraph[][], int s, int t, int parent[]) {
        /* 
         * Create a visited array and mark all vertices as not
         * visited
         */
        boolean visited[] = new boolean[V];
        for(int i=0; i<V; ++i)
            visited[i]=false;
        /* 
         * Create a queue, enqueue source vertex and mark
         * source vertex as visited
         */
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.add(s);
        visited[s] = true;
        parent[s]=-1;
        // Standard BFS Loop
        while (queue.size()!=0)
        {
            int u = queue.poll();
            for (int v=0; v<V; v++)
            {
                if (visited[v]==false && rGraph[u][v] > 0)
                {
                    queue.add(v);
                    parent[v] = u;
                    visited[v] = true;
                }
            }
        }
        /*
         * If we reached sink in BFS starting from source, then
         * return true, else false
         */
        return (visited[t] == true);
    }
    // Returns tne maximum flow from s to t in the given graph
    int fordFulkerson(int graph[][], int s, int t)
    {
        int u, v;
        /* 
         * Create a residual graph and fill the residual graph
         * with given capacities in the original graph as
         * residual capacities in residual graph
 		 */
        /*
         * Residual graph where rGraph[i][j] indicates
         * residual capacity of edge from i to j (if there
         * is an edge. If rGraph[i][j] is 0, then there is
         * not)
         */
        int rGraph[][] = new int[V][V];
        for (u = 0; u < V; u++)
            for (v = 0; v < V; v++)
                rGraph[u][v] = graph[u][v];
        // This array is filled by BFS and to store path
        int parent[] = new int[V];
        int max_flow = 0;  // There is no flow initially
        /* 
         * Augment the flow while tere is path from source
         * to sink
         */
        while (bfs(rGraph, s, t, parent))
        {
            /* 
             *Find minimum residual capacity of the edhes
             * along the path filled by BFS. Or we can say
             * find the maximum flow through the path found.
             */
            int pathFlow = Integer.MAX_VALUE;
            for (v=t; v!=s; v=parent[v])
            {
                u = parent[v];
                pathFlow = Math.min(pathFlow, rGraph[u][v]);
            }
            /* 
             * update residual capacities of the edges and
             * reverse edges along the path
             */
            for (v=t; v != s; v=parent[v])
            {
                u = parent[v];
                rGraph[u][v] -= pathFlow;
                rGraph[v][u] += pathFlow;
            }
            // Add path flow to overall flow
            max_flow += pathFlow;
        }
        // Return the overall flow
        return max_flow;
    }
    // Driver program to test above functions
    public static void main (String[] args) throws java.lang.Exception {
        // Example graph in adjancancy matrix
        int graph[][] =new int[][] { {0, 16, 13, 0, 0, 0},
                                     {0, 0, 10, 12, 0, 0},
                                     {0, 4, 0, 0, 14, 0},
                                     {0, 0, 9, 0, 0, 20},
                                     {0, 0, 0, 7, 0, 4},
                                     {0, 0, 0, 0, 0, 0}
                                   };
        FordFulkersonUsingBfs m = new FordFulkersonUsingBfs();
        System.out.println("The maximum possible flow is " +
                           m.fordFulkerson(graph, 0, 5));
    }
}

Python


'''
Part of Cosmos by OpenGenus Foundation
'''
from collections import defaultdict
#This class represents a directed graph using adjacency matrix representation
class Graph:
    def __init__(self,graph):
        self.graph = graph # residual graph
        self. ROW = len(graph)
        #self.COL = len(gr[0])   
    '''Returns true if there is a path from source 's' to sink 't' in
    residual graph. Also fills parent[] to store the path '''
    def BFS(self,s, t, parent):
        # Mark all the vertices as not visited
        visited =[False]*(self.ROW)     
        # Create a queue for BFS
        queue=[]      
        # Mark the source node as visited and enqueue it
        queue.append(s)
        visited[s] = True
        # Standard BFS Loop
        while queue: 
            #Dequeue a vertex from queue and print it
            u = queue.pop(0)
            # Get all adjacent vertices of the dequeued vertex u
            # If a adjacent has not been visited, then mark it
            # visited and enqueue it
            for ind, val in enumerate(self.graph[u]):
                if visited[ind] == False and val > 0 :
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u
        # If we reached sink in BFS starting from source, then return
        # true, else false
        return True if visited[t] else False    
    # Returns tne maximum flow from s to t in the given graph
    def FordFulkerson(self, source, sink):
        # This array is filled by BFS and to store path
        parent = [-1]*(self.ROW)
        max_flow = 0 # There is no flow initially
        # Augment the flow while there is path from source to sink
        while self.BFS(source, sink, parent) :
            # Find minimum residual capacity of the edges along the
            # path filled by BFS. Or we can say find the maximum flow
            # through the path found.
            path_flow = float("Inf")
            s = sink
            while(s !=  source):
                path_flow = min (path_flow, self.graph[parent[s]][s])
                s = parent[s]
            # Add path flow to overall flow
            max_flow +=  path_flow
            # update residual capacities of the edges and reverse edges
            # along the path
            v = sink
            while(v !=  source):
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]
        return max_flow
# Create a graph given in the above diagram
print("Enter the number of vertices: ", end="")
m = int(input())
matrix = []
for i in range(0,m):
    matrix.append([])
    for j in range(0,m):
        print("Enter the edge value from " + str(i) + " to " + str(j) +": ", end="")
        temp = int(input())
        matrix[i].append(temp)
print("\nthe matrix is,\n")
for i in range(0,m):
    for j in range(0,m):
        print(matrix[i][j]," ",end="")
    print("\n")
print("Enter the source: ", end="")
source = int(input())
print("Enter the sink: ", end="")
sink = int(input())
print ("The maximum possible flow is %d " % g.FordFulkerson(source, sink))

Applications

  • maximizing the transportation with given traffic limits
  • maximizing packet flow in computer networks.