Maximum flow

A flow network is a directed graph with a source s, a sink t, and a capacity on every edge: the most it can carry. A flow assigns each edge an amount that obeys two rules:

• no edge carries more than its capacity;
• every node other than s and t sends out exactly what comes in.

The maximum flow is the most that can leave s, and so arrive at t, under those rules. Water in pipes, data across links and goods along roads are the obvious cases. Less obvious ones, such as matching people to jobs, become flow problems too.

An augmenting path is a path from s to t on which every edge has room left. Find one with a breadth-first search that only follows edges with room. The amount you can push is the smallest room on the path, its tightest edge. Push it, and subtract it from the room of every edge on the path.

In the drawing, each label is the room left on that edge, so it starts at the capacity and falls as flow is pushed. The note under a node is the node the search reached it from.

To keep the code short, the search tries every node as a possible neighbor, so one search costs O(V²) for V nodes; with adjacency lists it would be O(V + E) for E edges. Flow pages write V and E for the node and edge counts that the graph pages call n and m.

Repeat the search and push until no path has room. It sounds complete, but it isn't. In this network the shortest path, s→a→b→t, takes 2 units and fills s→a and b→t. Every other route from s to t needs one of those two edges, so the search stops at 2.

Yet 3 units can get through: 1 along s→a→e→f→t, 1 along s→c→b→t and 1 along s→a→b→t. The first path sent 2 units through a→b, and one of them should have gone along a→e instead. A correct algorithm needs a way to take a unit back.

The fix is the residual graph. For each edge u→v carrying f units with capacity c, it has:

• u→v with residual capacity c − f, the room left;
• a reverse edge v→u with residual capacity f: sending flow "back" along it cancels some of the flow on u→v.

Searching the residual graph instead of the network, a path may use a reverse edge. Here, after the first push, the path s→c→b→a→e→f→t goes back along a→b: one unit that came from a to b now goes from a to e, and the unit arriving at b from c takes its place on b→t. Every node still sends out what it receives.

Repeating "find a path in the residual graph, push its tightest room" is the Ford-Fulkerson method. With integer capacities each push adds at least 1, so it ends. Choosing the path by breadth-first search, the shortest path in edges each time, is Edmonds-Karp, which needs at most O(V × E) pushes whatever the capacities are: O(V × E²) time with adjacency lists.

In the code, edge["a→b"] is the residual capacity from a to b. A reverse entry is created only where there is no real edge the other way; when both directions exist, a push adds to the real opposite edge's room instead. The drawing shows only the original edges; the reverse ones live in the code, and the narration says when the search uses one.

When the search finally can't reach t, the flow is maximum. Why that holds, and what the nodes the last search did reach tell you, is the subject of Minimum cut.

For interview-sized inputs Edmonds-Karp is the one to know: short, correct with any capacities, and fast enough for a few thousand edges.

LeetCode has few problems that need a flow algorithm: most problems that look like one are solved by matching, a plain search or bitmask dynamic programming, so the practice list below is short.