Max-Flow / Min-Cut: How Ford-Fulkerson Finds the Bottleneck

Flow networks and the residual graph

A flow network is a directed graph where every edge (u,v) has a capacity c(u,v) ≥ 0, with a source s and sink t. A valid flow must respect the capacity constraint on every edge and conservation at every internal vertex — exactly Kirchhoff's current law for water or electricity. The central idea behind every max-flow algorithm is the residual graph G_f, which tracks how much additional flow can still be pushed forward along an edge, and — crucially — how much existing flow can be "undone" by pushing in reverse. This reverse-edge trick is what lets an early greedy choice be partially cancelled later if it turns out to be suboptimal, without ever backtracking over the original graph.

Ford-Fulkerson and Edmonds-Karp

Ford and Fulkerson (1956) proposed repeatedly finding any augmenting path from s to t in the residual graph and pushing flow equal to its bottleneck capacity, until none remain. But the method doesn't specify how to find that path, and a naive DFS choice can require as many iterations as the maximum flow value — millions on a tiny graph with large integer capacities. Edmonds and Karp (1972) fixed this with one change: always take the shortest augmenting path via BFS. Because the shortest-path distance from s to any vertex is monotonically non-decreasing across iterations, each edge can become critical at most O(V) times, giving a genuine polynomial bound of O(VE²) independent of the capacity values.

The max-flow min-cut theorem

An s-t cut partitions the vertices into S (containing s) and T (containing t); its capacity is the total capacity of edges crossing from S to T. The max-flow min-cut theorem (Ford & Fulkerson, 1956) states that the maximum flow value exactly equals the minimum cut capacity over all such partitions — every unit of flow must cross the cut at least once (weak duality), and at the optimum every S→T edge is saturated while every T→S edge carries zero flow. This duality means finding the cheapest set of links to sever — the weakest point in a supply chain or the most vulnerable connections in a grid — falls out of a max-flow computation for free.

max |f|  over all valid flows f   =   min cap(S,T)  over all s-t cuts (S,T)

Edmonds-Karp:  O(V·E²)   (shortest augmenting path via BFS)
Dinic's:       O(V²·E) — O(E·√V) on unit-capacity graphs (bipartite matching)

Dinic's algorithm and bipartite matching

Dinic's algorithm (1970) builds a "level graph" via BFS, finds a blocking flow within it via DFS, then repeats — the BFS level of t strictly increases each phase, bounding the run to O(V) phases and O(V²E) overall, dropping to O(E√V) on unit-capacity graphs. That special case matters enormously: maximum bipartite matching — pairing workers to jobs, say — reduces directly to max-flow by adding a super-source and super-sink with capacity-1 edges everywhere. Because the integrality theorem guarantees an integer-valued optimal flow when all capacities are integers, the resulting flow is automatically a valid 0/1 matching, and Dinic's on this reduction is the celebrated Hopcroft-Karp algorithm in disguise.

Frequently asked questions

Try it live

Everything above runs in your browser — open Max-Flow / Min-Cut and step through Ford–Fulkerson (Edmonds–Karp) on a flow network: watch BFS find augmenting paths, push flow along the residual graph, then reveal the minimum cut. Nothing is installed, nothing is uploaded.