Push-Relabel Algorithm (Concept Level)

An introduction to the push-relabel maximum flow algorithm. Covers preflows, excess, height functions, and the two local operations -- push and relabel -- used to convert an initial preflow into a maximum flow.

Step 1 of 157%

Tutorial

Preflow, Excess, and Height

The push-relabel algorithm computes a maximum flow without ever searching for an augmenting path from $s$ to $t$ . Instead, it pushes flow locally between neighboring vertices using only their heights.

A preflow is like a flow, except conservation is relaxed: at every vertex $v \ne s$ , total flow in is allowed to exceed total flow out. The excess at $v$ is the amount currently stuck there:

e(v) = \sum_{u \in V} f(u,v) - \sum_{w \in V} f(v,w).

A vertex $v \notin \{s, t\}$ is active if $e(v) > 0$ .

Each vertex also has a nonnegative integer height $h(v)$ satisfying $h(s) = |V|$ , $h(t) = 0$ , and for every residual edge $(u,v)$ :

h(u) \le h(v) + 1.

Heights tell the algorithm which direction is "downhill" toward the sink.

Initialization. Set $h(s) = |V|$ and $h(v) = 0$ for $v \ne s$ . Saturate every edge leaving the source: $f(s, v) = c(s, v)$ for each $(s, v) \in E$ . All other edges start at $0$ . Every neighbor of $s$ that received flow becomes active.