Maximum Flow

The Maximum Flow problem asks: given a directed network where each connection has a limited capacity, what is the greatest amount of flow that can travel from a designated source to a designated sink?

This is a fundamental problem in graph theory and operations research, appearing in network design, traffic engineering, scheduling, and more. Understanding it deeply also gives you the tools to recognize when AI-generated solutions are subtly wrong.

What Is a Flow Network?#

A flow network is a directed graph where:

• Each edge has a capacity (maximum flow it can carry)
• There's a source vertex (where flow originates)
• There's a sink vertex (where flow ends)
• Flow is conserved at all other vertices (flow in = flow out)

Think of it like a network of water pipes: water enters at the source, travels through pipes that each have a diameter limit, and drains out at the sink. No water accumulates in the middle — everything that flows in must flow out. The question is: how much water can flow through the system per second?

Real-World Applications#

Max flow models any scenario where a limited-capacity network routes a resource from a supply point to a demand point:

Key Concepts#

Flow Constraints#

Every valid flow assignment must satisfy three constraints simultaneously:

Residual Graph#

The residual graph shows how much additional flow can be pushed through each edge:

• Forward edge: remaining capacity = capacity − current flow
• Backward edge: allows undoing flow, with capacity = current flow

Backward edges are what make the algorithm powerful — they let the algorithm reconsider earlier routing decisions. Without them, the algorithm could get locked into a suboptimal solution that blocks a better one.

Augmenting Path#

An augmenting path is a path from source to sink in the residual graph where every edge has positive residual capacity. The minimum residual capacity along the path is called the bottleneck — it determines the maximum additional flow we can push in a single step. We route that amount of flow through every edge on the path and update the residual graph accordingly.

Ford-Fulkerson Method#

The Ford-Fulkerson method is a general framework — not a single fixed algorithm — for solving max flow. It repeatedly finds an augmenting path in the residual graph, pushes as much flow as the bottleneck allows, and updates the residual graph. This repeats until no augmenting path from source to sink remains, at which point the flow is maximum.

Step-by-Step Example#

Each row shows the residual graph (left, with the augmenting path highlighted) used to find the next path, and the flow network (right) after pushing flow along that path. Dashed backward edges in the residual represent cancellable flow.

Edmonds-Karp Algorithm#

Edmonds-Karp is Ford-Fulkerson with one key implementation choice: always use BFS to find the shortest augmenting path (fewest edges).

This matters because Ford-Fulkerson with DFS can be extremely slow — if edge capacities are large integers, DFS may find paths that push only 1 unit of flow at a time, requiring millions of iterations. BFS avoids this trap: it can be proven that augmenting paths never get shorter over time when you always pick the shortest one, which limits the total number of augmentations to O(V × E). Since each BFS takes O(E) time, the overall complexity is O(V × E²) — polynomial regardless of edge capacity values.

Max-Flow Min-Cut Theorem#

One of the most important results in combinatorial optimization:

Maximum Flow = Minimum Cut

A cut is a partition of all vertices into two sets: S (containing the source) and T (containing the sink). The capacity of a cut is the total capacity of edges that go from S to T — these are the edges that, if removed, would disconnect the source from the sink.

Intuitively, any flow from source to sink must cross every cut, so no flow can exceed the capacity of any cut. The remarkable insight of this theorem is that there always exists a cut whose capacity exactly equals the maximum flow. This minimum cut identifies the true bottleneck of the network.

Finding the Min Cut#

After running max flow, the min cut consists of:

• S = the set of vertices reachable from source in the residual graph
• T = the set of vertices not reachable from source
• Cut edges = edges from S to T in the original graph

Bipartite Matching#

A classic application of max flow is finding the maximum matching in a bipartite graph.

A bipartite graph splits vertices into two disjoint groups — for example, jobs and workers — with edges running only between the groups (never within a group). A matching assigns each left vertex to at most one right vertex. The goal is to maximize the number of such paired assignments.

Max flow solves this elegantly: add a super-source connected to every left vertex, connect every right vertex to a super-sink, and set all edge capacities to 1. Running max flow on this network gives you the maximum matching — the flow value equals the number of matched pairs.

Algorithm Comparison#

Different max flow algorithms suit different scenarios. The right choice depends on graph density, the size of edge capacities, and whether unit capacities apply:

Reviewing AI-Generated Code#

Max flow is deceptively tricky to implement correctly. AI tools often produce code that looks reasonable but quietly computes the wrong answer — for instance, by forgetting backward edges or searching the wrong graph. Understanding the fundamentals gives you a reliable checklist to catch these mistakes:

What to Verify#

Common AI Pitfalls#

Questions to Ask AI#

When reviewing an AI-generated max flow implementation, use these prompts to probe correctness:

• "How do backward edges work in your residual graph?"
• "What path-finding strategy are you using, and how does that affect complexity?"
• "How would you extract the minimum cut from the residual graph after max flow?"
• "Walk me through your residual graph initialization — are reverse edges included?"

Summary#

Maximum flow is a foundational technique in combinatorial optimization with applications well beyond network routing. The residual graph and the max-flow min-cut duality are the core insights that transfer to a broad class of problems — from bipartite matching to image segmentation to project scheduling.