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


