Push-Relabel (Max Flow)

Push-Relabel is one of the fastest classical algorithms for maximum flow. Instead of finding whole augmenting paths like Ford-Fulkerson, it works locally: it lets nodes temporarily overflow, then shoves that overflow downhill one edge at a time, raising a node's "height" whenever it gets stuck.

The slow way first

The textbook approach (Ford-Fulkerson / Edmonds-Karp) repeatedly searches for a full path of unused capacity from s to t and pushes flow along it. Each search is a whole graph traversal, and on dense graphs you may need many of them. That makes it feel global: every step touches the entire path from source to sink.

The question to ask: can I make progress with only local information — looking at one node and its neighbors — instead of hunting for a complete path every time?

The idea: overflow, then push downhill

Push-Relabel keeps two numbers per node: a height h and an excess e (flow that has arrived but not yet left). It starts by saturating every edge out of the source — a "preflow" that deliberately overflows the source's neighbors. Then it fixes the overflow with two local moves:

A push moves excess across an edge u→v, but only if v is exactly one step lower (h[u] = h[v] + 1). A relabel raises a stuck node's height to one above its lowest reachable neighbor, so it can finally push. The source starts at height n so flow heads away from it; when no node except s and t overflows, the excess sitting at t is the answer.

Walk through it

Step through the animation. First h[s] is lifted to n = 4 and the source edges saturate, dumping excess onto a and b. Node a is stuck at height 0, so we relabel it and push toward t. It overflows again, relabels, and shoves the rest to b. Then b drains into t, and the leftover it cannot move forward is returned up the residual edge to s. When nothing overflows, e[t] = 4.

Pseudocode

h[v] = 0 for all v ;  e[v] = 0 for all v
h[s] = n                              # source sits at height n
for each edge s->v:                   # saturate the source (preflow)
    send full capacity s->v
    e[v] += capacity ;  e[s] -= capacity
while some node u (not s, not t) has e[u] > 0:
    if there is an edge u->v with residual > 0 and h[u] == h[v] + 1:
        push min(e[u], residual(u,v)) along u->v     # downhill push
    else:
        h[u] = 1 + min(h[v] over residual neighbors) # relabel (lift)
return e[t]                            # excess at the sink = max flow

The Python solution

def push_relabel(C, s, t, n):
    h = [0] * n
    e = [0] * n
    h[s] = n
    for v in range(n):                 # saturate source edges
        F[s][v] = C[s][v]
        e[v] = C[s][v]; e[s] -= C[s][v]
    while any(e[u] > 0 for u in nodes - {s, t}):
        u = an_overflowing_node()
        if exists v with res(u, v) > 0 and h[u] == h[v] + 1:
            push(u, v)                 # move flow to lower neighbor
        else:
            h[u] = 1 + min(h[v] for v in residual_neighbors(u))
    return e[t]                        # excess at sink = max flow

• h and e hold the height and excess of every node; both start at 0.
• h[s] = n lifts the source above everything so flow can only move away from it.
• Lines 5-7 build the preflow: every source edge is filled, and that flow becomes excess on the neighbor (the source's own excess goes negative — it is allowed to oversupply).
• The while loop runs as long as any node except s and t overflows.
• A node either pushes (line 11) when it has a downhill admissible edge, or relabels (line 13) to lift itself just above its lowest neighbor when stuck.
• When the loop ends, e[t] — the excess piled up at the sink — is the maximum flow.

Complexity

The big win over path-based methods is that progress is local — a single push or relabel touches one node and one edge, never a whole source-to-sink path. With good selection rules (highest-label, FIFO) push-relabel is among the fastest max-flow algorithms in practice.

When this pattern shows up

Practice