Here is the Edmonds-Karp implementation structure:
function edmondsKarp(n, source, sink, capacity):
flow = 0
while true:
// BFS to find augmenting path
parent = array of size n, all -1
visited = array of size n, all false
queue.push(source)
visited[source] = true
while queue is not empty and not visited[sink]:
u = queue.pop()
for v in adj[u]:
if not visited[v] and capacity[u][v] > 0:
visited[v] = true
parent[v] = u
queue.push(v)
if not visited[sink]:
break
// Find bottleneck
bottleneck = infinity
v = sink
while v != source:
u = parent[v]
bottleneck = min(bottleneck, capacity[u][v])
v = u
// Update capacities
v = sink
while v != source:
u = parent[v]
capacity[u][v] = capacity[u][v] - bottleneck
capacity[v][u] = capacity[v][u] + bottleneck
v = u
flow = flow + bottleneck
return flow
Time: . Space: .