The Edmonds-Karp algorithm finds the max flow on the
The difference between this algorithm and the Ford-Fulkerson method is that the search order is defined when finding the augmenting path. To find the path, we use a breadth-first search(BFS) by applying the weight of 1 to every edge. The path found by BFS must be the shortest one with the available capacity.
The following is a basic pseudo-code for Edmonds-Karp:
inputs:C[n x n] : Capacity MatrixE[n x n] : Adjacency Matrixs : sourcet : sinkoutput:f : maximum flowEdmonds-Karp:f = 0;res_graph = net_graphwhile res_graph contains an s − t path P do:Suppose P be an s − t path in the residual_graph with of edges.P = Breadth-First-Search(C, E, s, t, F)Augment maximum_flow using P.u = P[v]F[u, v] = F[u, v] - mUpdate residual_graphF[v, u] = F[v, u] + mv = uend whilereturn maximum_flow
For the given network of seven nodes, apply the Edmonds-Karp algorithm to find the max flow:
The pair
Note: The residual capacity = Total capacity - flow already used.
Following is the C++ code implementation of this pseudo-code:
// It will Returns tne maximum flow in the networkint Edmonds_Karp(int graph[V][V], int s, int t){int u, v;//Create a residual graph and fill with given capacitiesint rGraph[V][V]; // rGraph[i][j] indicates// residual capacity of edge from i to jfor (u = 0; u < V; u++)for (v = 0; v < V; v++)rGraph[u][v] = graph[u][v];int parent[V]; // This will store path find by BFSint max_flow = 0; // Algorithm will start with zero flow// Augment the flow while tere is path from source to sinkwhile (bfs(rGraph, s, t, parent)){// Find the maximum flow// through the path found by BFS.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 pathfor (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 flowmax_flow += path_flow;}// Returns max flowreturn max_flow;}
Line 16: The flow is initially zero, max_flow = 0
.
Line 18: The initial residual capacity array is all zeros. The outer loop will execute until there are no more paths from the source to sink into the residual graph bfs(rGraph, s, t, parent)!=false
. Inside the loop, we perform BFS to find the shortest path from source to sink with the available capacity.
Lines 31–38: After finding the shortest path with the residual capacity, we add that capacity to our maximum flow, and then it backtracks from the sink t
to find the parent of the vertex u = parent[v]
. It will update the residual flow matrix f
for the newly found augmenting path capacity m
.
Finally, v
set as the parent and inner loop repeated till it reaches the source vertex, and then it will return the max_flow
.
The big-O notation for this algorithm is