📅 July 2026⏱ 13 min🟡 Intermediate·Last updated: 3 July 2026
Max-Flow and Network Flows: How Ford-Fulkerson Works
How much water can flow through a network of pipes before some bottleneck limits it? How many packets per second can travel across the internet from a source server to a destination? The maximum-flow problem answers exactly this question, and its solution — the max-flow min-cut theorem — is one of the most elegant and useful results in all of algorithmic graph theory.
A flow network is a directed graph G = (V, E) where every edge (u, v) has a non-negative capacity c(u,v) ≥ 0 — the maximum amount of "stuff" (water, current, data, goods) that can pass through it. Two special vertices are singled out: a source s (where flow originates) and a sink t (where flow terminates).
A flow is a function f(u,v) assigning a real number to every edge, subject to two constraints:
Flow network constraints:
1. Capacity constraint:
0 ≤ f(u,v) ≤ c(u,v) for every edge (u,v)
2. Flow conservation:
Σ f(v,u) = Σ f(u,w) for every vertex u ≠ s,t
(flow in) (flow out)
The value of a flow |f| is the net flow leaving the source:
|f| = Σ f(s,v) − Σ f(v,s)
v∈V v∈V
Goal: find a flow f that maximises |f| subject to (1) and (2).
Conservation is the same principle behind Kirchhoff's current law in electrical circuits: whatever flows into an internal node must flow back out — nothing is created or destroyed except at the source and sink. This is what makes flow networks a natural model for physical transport systems as well as abstract ones like scheduling and matching.
2. Residual Graphs and Augmenting Paths
The central idea behind every max-flow algorithm is the residual graph G_f, which tracks how much additional flow can still be pushed along each edge — and crucially, how much flow can be "undone" by pushing in the reverse direction.
Residual capacity:
c_f(u,v) = c(u,v) − f(u,v) (remaining forward capacity)
c_f(v,u) = f(u,v) (capacity to "cancel" existing flow)
Residual graph G_f contains edge (u,v) whenever c_f(u,v) > 0.
An augmenting path P is any path from s to t in G_f.
Its bottleneck capacity is:
Δ = min{ c_f(u,v) : (u,v) ∈ P }
Pushing Δ units of flow along P:
for each edge (u,v) in P:
f(u,v) += Δ if (u,v) is a forward edge
f(v,u) -= Δ if (u,v) is a backward (reverse) edge
The reverse edges are the trick that makes the method correct: an early greedy choice can be partially "cancelled" later if it turns out to be suboptimal, letting the algorithm effectively reroute flow without ever needing to backtrack over the original graph structure.
3. The Ford-Fulkerson Method
Ford and Fulkerson (1956) proposed the simplest possible strategy: repeatedly find any augmenting path in the residual graph and push as much flow as its bottleneck allows, until no augmenting path remains.
FORD-FULKERSON(G, s, t):
for each edge (u,v) in E:
f(u,v) = 0
while there exists an augmenting path P from s to t in G_f:
Δ = min residual capacity along P
for each edge (u,v) in P:
augment f along (u,v) by Δ # update forward/backward
rebuild G_f
return f # f is now a maximum flow
Termination:
If all capacities are integers, each augmentation increases |f|
by at least 1, and |f| is bounded above by the total capacity
out of s → guaranteed to terminate for integer capacities.
With irrational capacities, Ford-Fulkerson can fail to terminate
at all — a classic pathological example (Ford & Fulkerson, 1962).
Why "any" path is dangerous: Ford-Fulkerson does not specify how to find the augmenting path — using plain DFS can pick pathologically bad paths repeatedly, requiring up to |f_max| iterations even on tiny graphs. On a graph with capacity 1,000,000 and only two paths of capacity 1 that alternately saturate and cancel each other, naive DFS-based Ford-Fulkerson needs 2,000,000 iterations. This motivated Edmonds-Karp.
4. Edmonds-Karp: Guaranteeing Polynomial Time
Edmonds and Karp (1972) fixed the pathological worst case with one change: always choose the shortest augmenting path (fewest edges), found via breadth-first search (BFS) rather than DFS.
EDMONDS-KARP(G, s, t):
f = 0 on all edges
while BFS(G_f, s, t) finds a path P:
Δ = min residual capacity along P
augment f along P by Δ
return f
Complexity analysis:
Each BFS takes O(E).
Key lemma: the shortest-path distance from s to any vertex in
G_f is monotonically non-decreasing across iterations.
Each edge can become "critical" (saturate the bottleneck)
at most O(V) times over the whole run.
Total number of augmentations: O(VE)
Overall time complexity: O(V E²)
Compare to naive Ford-Fulkerson: O(E · |f_max|) — unbounded by
V or E alone, and can be exponential for irrational or huge
integer capacities.
Edmonds-Karp is the textbook standard because its complexity is a genuine polynomial bound independent of the capacity values themselves — a property naive Ford-Fulkerson lacks entirely.
5. The Max-Flow Min-Cut Theorem
An s-t cut is a partition of the vertices into two sets S and T = V \ S, with s ∈ S and t ∈ T. The capacity of the cut is the total capacity of edges crossing from S to T. Intuitively, a cut represents a "bottleneck" — a set of pipes that, if severed, would completely disconnect the source from the sink.
Max-Flow Min-Cut Theorem (Ford & Fulkerson, 1956):
max |f| over all valid flows f
=
min cap(S,T) over all s-t cuts (S,T)
where cap(S,T) = Σ c(u,v) for u∈S, v∈T, (u,v)∈E
Proof sketch:
(≤) Weak duality: any flow value is ≤ any cut capacity, because
every unit of flow from s to t must cross the cut at least once.
(=) At the optimum: when Ford-Fulkerson terminates, no augmenting
path exists. Let S = vertices reachable from s in G_f,
T = the rest. Every edge crossing S→T must be saturated
(f = c), and every edge T→S must carry 0 flow (else it would
be a residual edge back into S). Hence |f| = cap(S,T) exactly,
proving the flow found equals this particular cut's capacity
— which must therefore be the minimum.
This duality is not just theoretical elegance — it means every max-flow algorithm is simultaneously a min-cut algorithm. Finding the minimum set of edges to remove to disconnect two nodes (e.g. the weakest links in a supply chain, or the most vulnerable connections in an electrical grid) is solved for free once you compute max flow.
6. Dinic's Algorithm and Faster Methods
Dinic's Algorithm (1970) — O(V² E):
Repeat:
1. Build a "level graph" via BFS from s (each vertex labelled
by its shortest-path distance from s in G_f).
2. Find a blocking flow in the level graph using DFS — a flow
where every s-t path is saturated at least once.
3. Add the blocking flow to f; rebuild the level graph.
Until t is unreachable from s in G_f.
Key fact: the BFS "level" of t strictly increases after each
phase → at most V phases. Each blocking flow computation costs
O(VE) → total O(V² E).
On unit-capacity graphs (e.g. bipartite matching), Dinic's runs
in O(E √V) — dramatically faster.
Even faster (for reference):
Push-relabel (Goldberg-Tarjan, 1988): O(V² E) amortised, fast in practice
Push-relabel + highest-label + gap: O(V² √E)
Orlin's algorithm (2013): O(VE) — matches theoretical lower bound
In practice, Dinic's algorithm (sometimes called Dinitz's algorithm) is the workhorse used in competitive programming and many production systems because it combines a strong worst-case bound with excellent real-world performance, especially on the near-unit-capacity graphs that arise from matching problems.
7. Bipartite Matching via Max-Flow
One of the most useful reductions in all of algorithms: maximum bipartite matching — pairing up two disjoint sets of vertices (e.g. workers to jobs, students to schools) so that each pairing respects allowed edges and no vertex is matched more than once — can be solved directly with max-flow.
Reduction: Bipartite Matching → Max-Flow
Given bipartite graph with parts L (left) and R (right):
1. Add a super-source s connected to every vertex in L,
capacity 1 on each edge.
2. Add a super-sink t connected from every vertex in R,
capacity 1 on each edge.
3. Every original edge (l, r) gets capacity 1, directed l → r.
Claim: max flow in this network = size of maximum matching.
Why: because all capacities are 1 and flow is integral
(integrality theorem — if all capacities are integers, there
exists a maximum flow that is integer-valued on every edge),
each unit of flow from s to t traces exactly one l→r pairing,
and conservation ensures no vertex is used twice.
With Dinic's algorithm this runs in O(E √V) — this specific
case is the celebrated Hopcroft-Karp algorithm in disguise.
Integrality theorem: If every edge capacity in a flow network is an integer, then there exists a maximum flow in which the flow on every single edge is also an integer. This is what guarantees the bipartite-matching reduction actually produces a valid 0/1 matching rather than fractional pairings — a property that does not hold for general linear programs without extra structure.
8. Real-World Applications
Network reliability & capacity planning: ISPs model backbone links as a flow network to find the maximum sustainable data rate between two data centres, and the min-cut identifies exactly which physical links form the bottleneck worth upgrading.
Airline & logistics scheduling: Assigning aircraft to routes, or trucks to delivery jobs, is frequently modelled as a flow problem with time-expanded networks — vertices represent (location, time) pairs and edges represent feasible movements.
Image segmentation (computer vision): The Boykov-Kolmogorov min-cut/max-flow algorithm segments foreground from background in an image by modelling pixels as graph nodes, with edge weights based on colour similarity — solved as a min s-t cut.
Sports elimination: Determining whether a team can still mathematically win a league is a classic max-flow reduction — remaining games are sources, teams needing wins are sinks, and if max flow saturates all source edges the team is not yet eliminated.
Project selection & baseball elimination: Choosing which subset of interdependent projects maximises profit subject to prerequisite constraints reduces to a min-cut computation on a "project selection" graph.
Circulation with lower bounds: Generalising max-flow to require a minimum flow on some edges (not just a capacity ceiling) models real supply chains where some pipeline must carry at least a contracted minimum — solved with an extended Ford-Fulkerson formulation.
Complexity context: Max-flow sits firmly in P — polynomial-time solvable, and modern algorithms (Orlin 2013, and near-linear approximate methods using electrical-flow techniques from 2013 onward) push ever closer to the theoretical O(VE) lower bound. This tractability is precisely why so many seemingly unrelated combinatorial problems — matching, scheduling, segmentation, elimination — are deliberately reformulated as flow problems: once expressed as a flow network, an NP-hard-looking problem often becomes solvable in polynomial time.