Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Reading time: 15 minutes | Coding time: 10 minutes
Edmonds–Karp algorithm is an optimized implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in O(V E^2) time instead of O(E |max_flow|) in case of Ford-Fulkerson algorithm.
The algorithm is identical to the Ford–Fulkerson algorithm, except that the search order when finding the augmenting path is defined. The path found must be a shortest path that has available capacity. This can be found by a breadth-first search, where we apply a weight of 1 to each edge. The running time of O(V E2) is found by showing that each augmenting path can be found in O(E) time, that every time at least one of the E edges becomes saturated (an edge which has the maximum possible flow), that the distance from the saturated edge to the source along the augmenting path must be longer than last time it was saturated, and that the length is at most V. Another property of this algorithm is that the length of the shortest augmenting path increases monotonically.
Pseudocode
maximum_flow = 0; residual_graph = network_graph
while residual_graph contains an s − t path P do:
Let P be an s − t path in residual_graph with the minimum number of edges.
Augment maximum_flow using P.
Update residual_graph
end while
return maximum_flow
Complexity
- Worst case time complexity:
Θ(V * E * E) - Average case time complexity:
Θ(V * E * E) - Best case time complexity:
Θ(V * E * E) - Space complexity:
Θ(E + V)
Proof of complexity:
2 Key ideas:
-
In the residual network, the distance of any vertex from the source never decreases during the algorithm.
-
Any edge can become critical at most O(V) times.
Implementations
- C++
- Java
- Python
C++
#include <iostream>
// Part of Cosmos by OpenGenus Foundation //
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;
#define V 6
/* Returns true if there is a path from source 's' to sink 't' in
* residual graph. Also fills parent[] to store the path */
bool bfs(int rGraph[V][V], int s, int t, int parent[])
{
// Create a visited array and mark all vertices as not visited
bool visited[V];
memset(visited, 0, sizeof(visited));
// Create a queue, enqueue source vertex and mark source vertex
// as visited
queue <int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
// Standard BFS Loop
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v = 0; v < V; v++)
if (visited[v] == false && rGraph[u][v] > 0)
{
q.push(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[V][V], 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
int rGraph[V][V]; // 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)
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
int parent[V]; // This array is filled by BFS and to store path
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 edges along the
// path filled by BFS. Or we can say find the maximum flow
// through the path found.
int path_flow = INT_MAX;
for (v = t; v != s; v = parent[v])
{
u = parent[v];
path_flow = min(path_flow, 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] -= path_flow;
rGraph[v][u] += path_flow;
}
// Add path flow to overall flow
max_flow += path_flow;
}
// Return the overall flow
return max_flow;
}
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
Applications of Edmonds Karp Algorithm are:
-
Finding the maximum flow in a flow network
-
Maximizing the transportation with given traffic limits
-
Maximizing packet flow in computer networks.
