Edmonds-Karp and Dinic’s Algorithms for Maximum Flow

Edmonds-Karp is a maximum flow algorithm. This is a specific implementation of the Ford-Fulkerson algorithm that uses different techniques for finding augmenting paths.

The Ford-Fulkerson method is used to find the maximum flow. Maximum flow is very useful for finding bipartite matching.
At a high level, Ford-Fulkerson says that we want to repeatedly find an augmenting path from source to sink (s->t) in the flow graph, augment flow and repeat until no more paths exist.

The key takeaway here is that the Ford-Fulkerson method does not specify how to actually find augmenting paths. This is where optimizations come into play. There are many articles where we see that this method uses a DFS to find augmenting paths that take O(Ff) where E is the number of the edges and f is the maxflow.

Each edge of the flow graph has a certain flow and capacity specified by the fraction adjacent to each edge. Initially, the flow through each edge is 0 and the capacity is non-negative.

To find the maximum flow (and min-cut as a product) the Ford-Fulkerson method repeatedly finds augmenting graphs through the residual graphs and augments the flow until no more augmenting paths can be found.

Credits for the image go to jakobkogler, DamianArado, adamant-pwn, infalmo, LUTLJS, Aryamn, Kakalinn, obiwac, shivensinha4, lm10-piyush, ShayekhBinIslam, wikku, roll-no-1.

Edmonds-Karp Algorithm:

The Edmonds-Karp algorithm is a modified form of the Ford-Fulkerson algorithm. The difference Is that Ford-Fulkerson uses the DFS approach and Edmonds-Karp uses the BFS approach.
The time complexity of this algorithm Is O(E^2) for irrational capacities and maximum longest path from source to sink.

Implementation

Here we use the BFS approach so we will make a 2-D array where we store the capacity of each vertex .We will also have an adjacency list for storing graphs because we will reverse the graph for finding an augmenting path.
The function maxflow is used to get the maximum value of a network from a 2-D array which is already created.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def bfs(arr, dp, source, sink):
  q = [source]
paths = {
  source: []
}
if source == sink:
  return paths[source]
while queue:
  u = queue.pop(0)
for neigh in range(len(arr)):
  if arr[u][neigh] - dp[u][neigh] > 0 and neigh not in paths:
  paths[neigh] = paths[u] + [(u, neigh)]
print(paths)
if neigh == sink:
  return paths[neigh]
q.append(neigh)
return
def max_flow(arr, source, sink):
  n = len(arr)
dp = [[0] * n
  for i in range(n)]
path = bfs(arr, dp, source, sink)
while path != None:
  flow = min(arr[u][v] - dp[u][v]
    for u, v in path)
for u, v in path:
  dp[u][v] += flow
dp[u][v] -= flow
path = bfs(arr, dp, source sink)
return sum(dp[source][i]
  for i in range(n))

Time complexity:

The time complexity of the Edmonds-Karp algorithm is O(VE^2) and space complexity is O(E+V), here E and V are the edges and vertices.

Applications:

1. Maximum flow algorithm

2. Packet transfer on transport layer in computer network

3. Traffic flow control on roads

Dinic’s Algorithm:

Like the Ford-Fulkerson and Edmonds-Karp algorithms for finding maximum flow, Dinic’s algorithm is efficient for finding network flow of unweighted bipartite graphs. Dinic’s algorithm is fast and convenient. Here we work on combining multiple graph traversal techniques together.
Dinic’s is a strongly polynomial maximum flow algorithm with a runtime of O(VE^2).
It is extremely fast and works better on bipartite graphs, giving time complexity of O(VE^(1/2)) due to algorithm reduction.
The algorithm was invented by Yefim Dinitz in 1969 and published in 1970.

Implementation

1. Construct a level graph by doing a BFS from the source to sink, all the levels of the current flow graphs.

2. If the sink was never reached while building the level graph, then stop and return the maxflow.

3. Using only valid edges in the level graph, do multiple DFS from source to sink (s->t) until blocking flow is reached to sum the bottleneck values of all the augmenting paths found to calculate the maxflow.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def Bfs(C, First, s, t): # C is the capacity matrix
n = len(C)
queue = []
queue.append(s)
global steps
steps = n * [0] # initialization
steps[s] = 1
while queue:
  k = queue.pop(0)
for i in range(n):
  if (First[k][i] < C[k][i]) and(steps[i] == 0): # not visited
steps[i] = steps[k] + 1
queue.append(i)
return steps[t] > 0

#search augmenting path by using DFS
def Dfs(C, F, k, cp):
  tmp = cp
if k == len(C) - 1:
  return cp
for i in range(len(C)):
  if (level[i] == level[k] + 1) and(F[k][i] < C[k][i]):
    f = Dfs(C, F, i, min(tmp, C[k][i] - F[k][i]))
F[k][i] = F[k][i] + f
F[i][k] = F[i][k] - f
tmp = tmp - f
return cp - tmp

#calculate max flow
#_ = float('inf')
def MaxFlow(C, s, t):
  n = len(C)
F = [n * [0]
  for i in range(n)] # F is the flow matrix
flow = 0
while (Bfs(C, F, s, t)):
  flow = flow + Dfs(C, F, s, 100000)
return flow

Comparison Among Various Algorithms

We have already read about Edmonds-Karp and Dinic’s algorithms. Now let’s look at a comparison of all the algorithms for maximum flow in a graph.

Ford-Fulkerson Max Flow Algorithm:

For the max flow f*, the maximum value |f*| denotes a bound in the number of iterations. Total running time is O(|f*|m).
Edmonds-Karp Algorithm:
Worst case time complexity O(|f*|m) to O(nm²).

Goldberg-Tarjan Algorithm:

Time complexity is O(n²m).
Below is a tabular analysis of all algorithms.