liveBook · Manning

Maximum flow

As explained in Algorithms Every Programmer Should Know

The problem of finding the greatest feasible flow from a source to a sink in a capacitated network.

Imagine a streaming pipeline whose connections can each carry only so much data. Maximum flow asks: what is the greatest total throughput that can travel from its source to its sink without exceeding any connection’s capacity? A tempting approach is to find a complete route, send as much as its narrowest connection permits, and repeat. Push–Relabel takes a different approach: it moves flow locally instead of repeatedly searching for end-to-end routes. section 10.0 section 10.1

Figure 10.1 Source (s) connects to Node 1 (capacity 10) and Node 2 (capacity 5). Node 1 connects to Node 2 (capacity 15) and to Sink t (capacity 10). Node 2 connects to Sink t (capacity 10). The notations ‘h’ and ‘e’ denote the height of the vertex and the excess capacity of the vertex it can hold respectively.

Use this four-node network to follow how 15 units leave the source, move between two intermediate nodes, and ultimately reach the sink. section 10.1

Think of intermediate nodes as tanks that may temporarily hold more flow than they send onward:

  • Start with a preflow: fill the source’s outgoing connections to capacity. Any flow waiting at an intermediate node is its excess. section 10.4
  • An active node with excess pushes to a neighbor when unused capacity remains and the node’s height is exactly one greater than the neighbor’s. section 10.4
  • If it cannot push, relabel it: raise its height to one above the lowest reachable residual neighbor. Continue until no intermediate node has excess. section 10.4

Following 15 units

In the four-node network, the source sends 10 units to node 1 and 5 to node 2. One sequence has node 1 push its 10 units to node 2. Node 2 then sends 10 to the sink and pushes its remaining 5 back to node 1; node 1 sends those 5 to the sink. That backward move redirects flow rather than losing it. Both intermediate nodes finish with zero excess, and the sink receives 15 units—the maximum flow. section 10.1

The same question can test whether a baseball team is mathematically eliminated: capacities represent remaining games and the wins rival teams can still take without passing a target total. If the maximum flow cannot account for every remaining game, no permissible distribution of wins exists. For larger networks, implementation choices matter: generic Push–Relabel has an O(V³) time bound; capacity and flow matrices use O(V²) space, while adjacency lists can use O(V+E). section 10.2 section 10.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through preflow, excess, push, relabel, and a four-node trace, then gives implementation and complexity details.
Examples
Traces a four-node network carrying 15 units and models baseball elimination using remaining games and allowable wins.
What it assumes
Starts with source, sink, and connection capacities; develops preflow, excess, and height through a water-tank analogy.
What you can do after
Build it from scratch with a Python Push–Relabel implementation that computes source-to-sink maximum flow.
How it connects
Connects maximum flow to Ford–Fulkerson, augmenting paths, residual capacity, preflow, and Push–Relabel.

Also explained in

Compare how 3 books explain maximum flow →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.