Push-Relabel Operations
You'll learn how the push-relabel algorithm manipulates flow by pushing excess forward and relabeling nodes when paths are blocked.
Unlike Ford-Fulkerson-style algorithms that find entire augmenting paths, the push-relabel algorithm works locally—moving flow from one node to its neighbors using two fundamental operations.
The Core Operations
Push Operation
A push sends excess flow from a node to one of its neighbors in the residual network. Think of water flowing downhill: you can only push flow from a node at a higher "height" to a neighbor at a lower height (we'll see what "height" means in a moment).
There are two types:
- Saturating push: sends as much flow as the edge capacity allows
- Non-saturating push: sends all the excess flow from the source node (less than edge capacity)
A push from node u to v is valid only if:
uhas excess flow- There's residual capacity on edge
(u,v) uis one level higher thanvin the height function:height[u] = height[v] + 1
Relabel Operation
When a node has excess flow but cannot push to any neighbor (all neighbors are at the same or higher height), we relabel that node—raising its height. This is like lifting water in a basin: once raised, it can now flow to previously unreachable neighbors.
Relabeling sets height[u] to 1 + min(height[v]) for all neighbors v with residual capacity.
The Analogy
Imagine water pooling at different elevations. You can pour water from a higher pool to a lower one (push). If water is stuck with nowhere to go, you physically lift that pool higher (relabel) so it can pour elsewhere.
Key Takeaway: Push operations move excess flow toward the sink when height gradients allow; relabel operations adjust node heights to unblock stuck flow, maintaining the invariant that flow moves "downhill."