pushrelabel

Push-relabel, also known as the preflow-push algorithm, is an algorithm for computing the maximum s–t flow in a directed graph with capacities. It maintains a feasible preflow and a height function on vertices that guides flow toward the sink. The source is given a large height and initially saturates all edges leaving it, creating excess flow at downstream vertices. The algorithm repeatedly selects an active vertex (one with positive excess, excluding the sink) and either pushes flow toward a neighboring vertex or, if no push is possible, relabels the vertex to enable further pushes.

Push operation: if there is residual capacity on an edge (u,v) and the height satisfies h(u) = h(v) + 1, the algorithm pushes as much as possible from u to v, reducing excess at u and increasing excess at v. This may occur along multiple edges incident to u.

Relabel operation: when no admissible edge exists from an active vertex, its height is increased to the minimum height of its neighbors with residual capacity plus one, creating new admissible edges.

The process uses a residual graph throughout and ends when no active vertices remain besides the source and sink. The final preflow corresponds to a maximum s–t flow, with the value equal to the total excess emitted by the source.

Variants and heuristics improve performance. The global relabeling heuristic periodically recomputes vertex heights via a backward search from the sink, while the gap heuristic collapses a range of heights to reduce work. Common implementations include FIFO push-relabel and highest-label variants; together with heuristics, they perform well on large networks.

Push-relabel was introduced by Goldberg and Tarjan in 1986 and remains a practical, robust method for maximum flow computations.