Ford–Fulkerson (Maximum Flow)

Maximum flow sends as much stuff as possible from source to sink—Ford–Fulkerson augments along paths in the residual graph.

Why this shows up in the real world

Maps & routing, social networks, and dependency systems are modeled as graphs—vertices are places or tasks, edges are roads or prerequisites.

Core idea (explained for students)

Residual capacity c_f(u,v)=c(u,v)-f(u,v). BFS finds shortest augmenting path (Edmonds–Karp). Min-cut max-flow theorem links cuts to bottlenecks.

Try this in Python

from collections import deque


def bfs_shortest(adj: list[list[int]], start: int) -> list[int]:
    n = len(adj)
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist


print(bfs_shortest([[1, 2], [0], [0]], 0))

Common mistakes

• Infinite loop without capacity decrease on augment.
• Confusing flow problems with shortest path.

Key takeaways

• Bipartite matching reduces to flow with unit capacities.
• Start with BFS augmenting paths before Dinic for contests.