liveBook · Manning

Push-relabel algorithm

As explained in Algorithms Every Programmer Should Know

The push-relabel algorithm computes a maximum flow by maintaining a preflow and vertex height labels, then locally pushing excess flow and relabeling vertices.

Imagine water entering a pipe network faster than some junctions can drain it. Rather than plan a complete route from reservoir to outlet, let water collect at junctions and move it locally whenever a pipe has room. The push-relabel algorithm uses this approach to compute maximum flow from a source to a sink without repeatedly searching for an end-to-end augmenting path. section 10.0 section 10.1

Each vertex keeps two pieces of working state:

  • Excess is flow received but not yet sent onward. An intermediate vertex with positive excess is active; unlike an ordinary flow, a preflow permits this temporary imbalance. section 10.1
  • Height determines where excess may move. A push from u to v requires spare residual capacity and h(u) = h(v) + 1. If no such neighbor is available, relabel u to one above the lowest-height neighbor reachable through residual capacity. section 10.1 section 10.4

Start by setting the source height to the number of vertices, leaving other heights at zero, and saturating every outgoing source edge. Those pushes create excess at neighboring vertices. Repeatedly choose an active intermediate vertex, push what it can, and relabel it when it is stuck. A push can also send flow backward through a residual edge, undoing an earlier routing choice. Stop when no intermediate vertex has excess; the flow arriving at the sink is maximum. section 10.1 section 10.4

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 the four-vertex network to follow where excess accumulates and which edges can carry it. section 10.1

Fifteen units through four vertices

The source initially sends 10 units to vertex 1 and 5 to vertex 2. One valid sequence relabels vertex 1 and pushes its 10 units to vertex 2, leaving vertex 2 with 15. Vertex 2 sends 10 to the sink, then relabels and sends its remaining 5 back to vertex 1 through a residual edge. Vertex 1 sends those 5 to the sink. Both intermediate vertices finish with zero excess, and the sink receives 15 units. section 10.1

A Python implementation can store capacities, flows, heights, and excesses in arrays and process active vertices with a FIFO queue. The generic algorithm has an O(V³) time bound; capacity and flow matrices use O(V²) space, while adjacency lists use O(V + E). Active-vertex selection affects how much repeated work occurs. Beyond throughput networks, maximum-flow models can test baseball elimination: if not all remaining-game capacity can reach the sink, the team being tested is eliminated. section 10.1 section 10.2 section 10.3

How Algorithms Every Programmer Should Know covers it

How deep it goes
Develops preflow, excess, residual pushes, and relabeling through a complete small-network trace and Python routines.
Examples
Traces a four-vertex network to 15 units of flow and models baseball elimination using remaining games.
What it assumes
Assumes a capacity graph with a source and sink; develops preflow, excess, and height labels through a water analogy.
What you can do after
Build it from scratch with capacity and flow arrays, push and relabel routines, and a FIFO active queue.
How it connects
Connects maximum flow to residual graphs, augmenting paths, minimum cuts, and active-vertex scheduling.

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.