Maximum Flow

Picture a network of water pipes running from a source to a destination. Every pipe has a capacity — a maximum it can carry per second. Some pipes are fat, some are thin, and they join at junctions. The question is simple: how much water can you push from the source to the destination at once?

That's the maximum flow problem, and it isn't only about water. The "pipes" can be roads carrying cars, cables carrying data, or a supply chain carrying goods. Anywhere stuff moves through a network with limited links, max flow asks for the most you can send.

Here's the twist that makes this article special. Almost every problem on this site is easy to check but hard to solve. Max flow breaks the pattern: it looks tangled and complex, yet it has a beautiful, efficient solution. Sometimes the limits of algorithms bend in our favour.

Below is a small network. Water starts at S and must reach T; each pipe is labelled flow / capacity. The strategy is wonderfully simple: find any route from S to T that still has spare room, and push as much as the tightest pipe on it allows. Repeat. This is the idea of an augmenting path.

Press Find a path to send flow one route at a time, or Solve to go all the way. Watch the total climb — and then stall.

<p class="hint">{{hint}}</p>
<svg id="net" viewBox="0 0 360 280" role="img" aria-label="{{aria_flow_network}}">
  <defs>
    <marker id="arrow" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse">
      <path d="M0,0 L10,5 L0,10 z" fill="#888"></path>
    </marker>
    <marker id="arrowhi" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse">
      <path d="M0,0 L10,5 L0,10 z" fill="#e07a00"></path>
    </marker>
  </defs>
  <g id="edges"></g>
  <g id="nodes"></g>
</svg>
<p id="status" class="status"></p>
<div class="bar-btns">
  <button id="step" type="button">{{btn_find_path}}</button>
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .5rem; line-height: 1.45; }
svg { width: 100%; max-width: 360px; height: auto; display: block; margin: 0 auto; }
.elabel { font: 700 12px ui-monospace, monospace; fill: #333; paint-order: stroke; stroke: #fff; stroke-width: 3px; }
.nlabel { font: 700 15px system-ui; fill: #fff; text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.status { font-size: 1rem; font-weight: 700; min-height: 1.4em; margin: .5rem 0; line-height: 1.4; }
.status.ok { color: #0a7d33; }
.bar-btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

// Code not found

When no route has spare room left, you've hit the maximum. Notice why it stops: a set of pipes is completely full, and together they form a wall the flow can't get past. That wall is the key to the whole problem.

The wall you just hit has a name: a cut. A cut splits the network into two sides — the source's side and the sink's side — and its capacity is the total of the pipes crossing from one side to the other. The minimum cut is the cheapest such wall.

The celebrated max-flow min-cut theorem says something remarkable: the maximum flow you can push is exactly equal to the capacity of the minimum cut. The most you can send and the cheapest way to block everything are the same number.

It's a perfect example of duality — two questions that look opposite ("send the most" vs. "block with the least") turn out to be two views of one truth. In the demo, the red pipes at the end are the minimum cut: saturate them and nothing more can pass.

Now the payoff. Max flow is not NP-hard — it sits comfortably in P, the class of problems we can solve efficiently.

• The Ford–Fulkerson method keeps finding augmenting paths until none remain — exactly what the demo does.
• Choosing the shortest augmenting path each time (Edmonds–Karp) guarantees it finishes in polynomial time, no matter the capacities.
• Faster methods (Dinic's algorithm, push-relabel, and recent near-linear-time breakthroughs) make even enormous networks practical.

This is the encouraging mirror image of the P vs NP story. Max flow could have been a combinatorial nightmare — there are astronomically many ways to route flow — yet the augmenting-path insight tames it completely. A handful of beautiful ideas turn a seemingly hard problem into an everyday tool.

Because so many situations are "move as much as possible through a network", max flow shows up far beyond plumbing:

• Logistics and transport: maximize goods through a road, rail, or shipping network; find the bottleneck links.
• Telecommunications: route the most data through a network and identify the cables that limit it.
• Matching problems: assigning workers to jobs or students to schools becomes a max-flow problem (bipartite matching).
• Image segmentation: computer vision separates foreground from background by computing a minimum cut on a pixel network.
• Reliability and security: the minimum cut reveals the fewest links whose failure — or sabotage — would disconnect a network.

The min-cut side is just as useful as the max-flow side: one tells you the most you can achieve, the other tells you exactly where the weak point is.

Maximum flow is the optimist's problem. It looks every bit as tangled as the NP-hard puzzles elsewhere on this site, yet it yields to a single elegant idea — keep pushing along any path with room — and finishes fast every time. And as a bonus, it hands us the minimum cut: the precise bottleneck that limits everything.

It's a reminder that "looks complicated" and "is intractable" are different things. Some of the most useful problems in computing are exactly the ones that, once you find the right way to look at them, turn out to be wonderfully, provably easy.