Maximum Flow (Ford-Fulkerson)
DSA · Graphs
Theory
The maximum flow problem asks how much can be sent from a source to a sink through a network where each edge has a capacity, like water through pipes or data through network links. Ford-Fulkerson solves it by repeatedly finding an augmenting path, a path from source to sink that still has spare capacity, and pushing as much flow as the smallest capacity on that path allows. It keeps a residual graph: after sending flow along an edge, it reduces that edge's remaining capacity and adds a reverse edge so that later paths can undo earlier choices. When no augmenting path remains, the total flow is maximal. The max-flow min-cut theorem says this value equals the capacity of the smallest cut separating source and sink.
Why we use it
Many allocation problems reduce to max flow: matching applicants to jobs, routing traffic, scheduling, and finding bottlenecks in pipelines or supply chains.
When to use it
Use it when you need the most of something that can pass through a capacitated network, or the minimum set of edges whose removal disconnects source and sink.
How it works
- flow = 0, residual = capacities
- Augmenting path s -> t exists? Yes: b = smallest residual on path. No: Stop: flow is maximum.
- Push b: forward -= b, reverse += b
- flow = flow + b, repeat
Syntax
while augmenting path p exists in residual graph:
f = min residual capacity on p
push f along p (update forward and reverse edges)
DFS version: O(E * max_flow)Example
def max_flow(cap, s, t):
n = len(cap)
flow = 0
residual = [row[:] for row in cap]
def dfs(u, pushed, seen):
if u == t:
return pushed
seen.add(u)
for v in range(n):
if v not in seen and residual[u][v] > 0:
got = dfs(v, min(pushed, residual[u][v]), seen)
if got:
residual[u][v] -= got
residual[v][u] += got
return got
return 0
while True:
pushed = dfs(s, float("inf"), set())
if not pushed:
return flow
flow += pushed
# 0 = source, 5 = sink
cap = [
[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],
]
print("Maximum flow:", max_flow(cap, 0, 5))Key points
- Repeatedly push flow along augmenting paths
- Reverse edges in the residual graph let the algorithm undo choices
- Max flow equals min cut
- Bipartite matching is a special case