State
Each vertex has 'excess' (inflow - outflow) and 'height'. Push flow from higher to lower height. Relabel (increase height) when can't push.
Advertisement
Operations
Push: send min(excess, residual) from u to v if height[u] = height[v] + 1. Relabel: increase height[u] to min height of neighbors + 1.
Advertisement
Complexity
Generic: O(V²·E). FIFO: O(V³). Highest label: O(V²·√E).
Practice
Highest-label push-relabel often fastest max-flow in practice for dense graphs.