Get this book > Problems on Array: For Interviews and Competitive Programming
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 subroutine.
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:

What is the worst case scenario for Ford Fulkerson algorithm?

Will Ford Fulkerson algorithm terminate for all graphs?
Worst case scenario:
Flow increments by 1 in each step for a graph such as:
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.
Nonterminating example:
Ford Fulkerson algorithm will not terminate for the following graph:
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 FordFulkerson.
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.