To implement Edmonds–Karp we run repeated BFS from s to t on the residual graph to find the shortest (in edges) augmenting path, augment flow along it, and repeat until no path exists.python
from collections import deque
class Edge:
def __init__(self, to, rev, cap):
self.to = to # destination node
self.rev = rev # index of reverse edge in adj[to]
self.cap = cap # remaining capacity
def edmonds_karp(n, edges, s, t):
# build adjacency list with forward and reverse edges
adj = [[] for _ in range(n)]
def add_edge(u, v, c):
adj[u].append(Edge(v, len(adj[v]), c))
adj[v].append(Edge(u, len(adj[u]) - 1, 0))
for u, v, c in edges:
add_edge(u, v, c)
flow = 0
while True:
parent = [None] * n # (node, edge_index) to reconstruct path
q = deque([s])
parent[s] = (-1, -1)
while q and parent[t] is None:
u = q.popleft()
for ei, e in enumerate(adj[u]):
if e.cap > 0 and parent[e.to] is None:
parent[e.to] = (u, ei)
q.append(e.to)
if e.to == t:
break
if parent[t] is None:
break # no more augmenting paths
# find bottleneck
v = t
bottleneck = float('inf')
while v != s:
u, ei = parent[v]
e = adj[u][ei]
bottleneck = min(bottleneck, e.cap)
v = u
# augment
v = t
while v != s:
u, ei = parent[v]
e = adj[u][ei]
e.cap -= bottleneck
adj[e.to][e.rev].cap += bottleneck
v = u
flow += bottleneck
return flow
