DSA Graphs

Push-Relabel Algorithm

The pipeline floods from the reservoir first, then drains excess downhill tower by tower. Push-relabel works with a and , not one augmenting path at a time.

Active vertices with either push to a lower neighbor or . Heuristics make large dense nets practical.

Algorithm journey

Saturate source edges

Preflow + high source height.

Push excess downhill

Admissible residual edges only.

Raise height when stuck.

No active vertices

Preflow becomes a max flow.

What actually happens

Naive idea: only augmenting paths. Fine for teaching; can be slow on dense graphs with many overlapping routes.

Better idea: allow temporary excess. Push locally using heights as a potential. Relabel when a vertex has residual neighbors but none are downhill by exactly 1.

The improved design still fails without good discharge order / global relabel on hard instances, or if heights violate the admissible-edge invariant (then correctness proofs break).

Invariant

The state is always a valid preflow. For every residual edge u→v, h(u) ≤ h(v)+1. When no vertex (except s,t) has excess, the preflow is a maximum flow.

How to choose push-relabel

1. Large or dense networks? Often the practical winner.

2. Sparse contest matching? Dinic may be simpler to implement well.

3. Need simple code? Edmonds-Karp / Dinic first; add heuristics later.

Quantitative check

Generic bound O(V²E); with FIFO/highest-label heuristics much faster in practice. Global relabel every O(V) operations often dominates wall-clock time on real graphs.

Interactive demo

Operations: 0

Max Flow: 0

Click Play to initialize preflow!

0SRC

5SINK

Source

Sink

Has Excess

Active (Push/Relabel)

Push Edge

🎯 Key Insight: Height-Based Flow

Push-Relabel maintains height labels h[v] for each vertex. Flow can only be pushed downhill (from h[u] to h[v] where h[u] = h[v] + 1). When a vertex has excess but can't push to any neighbor, we relabel it by increasing its height. This local approach (no global path finding) makes it fast and parallelizable!

The four invariants to say out loud

Capacity remains feasible

Push at most min(excess[u], residual(u,v)), then update the paired reverse edge.

Preflow, not flow: yet

Internal vertices may have non-negative excess. When no active internal vertex remains, every one has zero excess, so conservation is restored.

Valid height labels

For every residual edge, h(u) ≤ h(v)+1. Only an edge with equality is admissible for a push.

Monotone progress

Heights only increase. A discharge either removes excess, saturates an edge, or raises a label.

Why the final flow is maximum: a valid labeling starts with h(s)=V and h(t)=0. A residual s–t path would need at least V edges, impossible for a simple path on V vertices. Once all internal excess is gone, the preflow is therefore a feasible flow with no augmenting path.

🔑 Key Concepts

Preflow

Unlike regular flow, a preflow allows nodes to have excess flow (more flow in than out). The algorithm starts by saturating all edges from the source, creating excess at neighboring nodes, then redistributes this excess.

Height/Distance Labels

Each vertex has a height h(v). Flow can only be pushed from a vertex u to v if h(u) = h(v) + 1 (downhill). The source starts at height n, and the sink at height 0.

Push Operation

When a vertex has excess flow and an edge to a lower neighbor with residual capacity, push as much flow as possible (min of excess and residual capacity) along that edge.

Relabel Operation

When a vertex has excess but can't push to any neighbor (all neighbors are too high or edges are saturated), increase its height to 1 + minimum height of neighbors with residual capacity.

🔍 Did You Know? No Augmenting Paths!

Unlike Ford-Fulkerson, Edmonds-Karp, and Dinic's, Push-Relabel never explicitly finds augmenting paths! Instead, it works locally at each vertex, pushing excess flow downhill based on height labels. This "local" approach makes it highly parallelizable and often faster in practice, especially for dense graphs!

📝 Algorithm Steps

Initialize Preflow

Set height[source] = n, height[all others] = 0. Saturate all edges from source (push maximum flow). This creates excess at all neighbors of the source.

Select Active Vertex

Choose a vertex with excess flow (not source or sink). Different selection strategies exist: FIFO, highest label, etc.

Push or Relabel

If the vertex can push to a lower neighbor with residual capacity, push flow. Otherwise, relabel the vertex (increase its height).

Repeat

Repeat steps 2-3 until no vertex has excess flow (except source). The flow reaching the sink is the maximum flow!

🎯 Key Insight: Height Invariant

The algorithm maintains a crucial invariant: h(u) ≤ h(v) + 1 for every residual edge (u, v). This ensures flow only moves "downhill" and prevents cycles. When we relabel a vertex, we set its height to1 + min(h(v)) for all neighbors v with residual capacity, maintaining the invariant!

Heights can never exceed 2V - 1, which bounds the number of relabel operations!

💻 FIFO Push-Relabel with paired residual edges

Python

python

from collections import deque

class Edge:
    def __init__(self, to: int, rev: int, residual: int) -> None:
        self.to, self.rev, self.residual = to, rev, residual

class PushRelabel:
    def __init__(self, n: int) -> None:
        if n <= 0:
            raise ValueError("n must be positive")
        self.graph = [[] for _ in range(n)]

    def add_edge(self, u: int, v: int, capacity: int) -> None:
        if not (0 <= u < len(self.graph) and 0 <= v < len(self.graph)):
            raise IndexError("vertex out of range")
        if u == v:
            raise ValueError("self-loops are not supported")
        if capacity < 0:
            raise ValueError("capacity must be non-negative")
        forward = Edge(v, len(self.graph[v]), capacity)
        reverse = Edge(u, len(self.graph[u]), 0)
        self.graph[u].append(forward)
        self.graph[v].append(reverse)

    def max_flow(self, source: int, sink: int) -> int:
        if not (0 <= source < len(self.graph) and 0 <= sink < len(self.graph)):
            raise IndexError("vertex out of range")
        if source == sink:
            raise ValueError("source and sink must differ")
        n = len(self.graph)
        height = [0] * n
        excess = [0] * n
        next_edge = [0] * n
        queued = [False] * n
        active = deque()

        def activate(v: int) -> None:
            if v not in (source, sink) and excess[v] > 0 and not queued[v]:
                queued[v] = True
                active.append(v)

        def push(u: int, edge: Edge) -> None:
            amount = min(excess[u], edge.residual)
            edge.residual -= amount
            self.graph[edge.to][edge.rev].residual += amount
            excess[u] -= amount
            excess[edge.to] += amount
            activate(edge.to)

        def relabel(u: int) -> None:
            neighbor_height = min(
                height[edge.to] for edge in self.graph[u] if edge.residual > 0
            )
            height[u] = neighbor_height + 1
            next_edge[u] = 0

        def discharge(u: int) -> None:
            while excess[u] > 0:
                if next_edge[u] == len(self.graph[u]):
                    relabel(u)
                    continue
                edge = self.graph[u][next_edge[u]]
                if edge.residual > 0 and height[u] == height[edge.to] + 1:
                    push(u, edge)
                else:
                    next_edge[u] += 1

        height[source] = n
        for edge in self.graph[source]:
            if edge.residual == 0:
                continue
            amount = edge.residual
            edge.residual = 0
            self.graph[edge.to][edge.rev].residual += amount
            excess[source] -= amount
            excess[edge.to] += amount
            activate(edge.to)

        while active:
            u = active.popleft()
            queued[u] = False
            discharge(u)
            activate(u)
        return excess[sink]

flow = PushRelabel(6)
for edge in [
    (0,1,16), (0,2,13), (1,2,10), (2,1,4), (1,3,12),
    (2,4,14), (3,2,9), (4,3,7), (3,5,20), (4,5,4),
]:
    flow.add_edge(*edge)
assert flow.max_flow(0, 5) == 23

Java

java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class PushRelabel {
    static final class Edge {
        final int to, rev;
        long residual;
        Edge(int to, int rev, long residual) {
            this.to = to; this.rev = rev; this.residual = residual;
        }
    }

    private final List<List<Edge>> graph;
    PushRelabel(int n) {
        if (n <= 0) throw new IllegalArgumentException("n must be positive");
        graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    }

    void addEdge(int u, int v, long capacity) {
        if (u < 0 || u >= graph.size() || v < 0 || v >= graph.size()) {
            throw new IndexOutOfBoundsException("vertex out of range");
        }
        if (u == v) throw new IllegalArgumentException("self-loop");
        if (capacity < 0) throw new IllegalArgumentException("negative capacity");
        Edge forward = new Edge(v, graph.get(v).size(), capacity);
        Edge reverse = new Edge(u, graph.get(u).size(), 0L);
        graph.get(u).add(forward);
        graph.get(v).add(reverse);
    }

    long maxFlow(int source, int sink) {
        if (source < 0 || source >= graph.size() || sink < 0 || sink >= graph.size()) {
            throw new IndexOutOfBoundsException("vertex out of range");
        }
        if (source == sink) throw new IllegalArgumentException("source == sink");
        int n = graph.size();
        int[] height = new int[n];
        int[] nextEdge = new int[n];
        long[] excess = new long[n];
        boolean[] queued = new boolean[n];
        ArrayDeque<Integer> active = new ArrayDeque<>();

        height[source] = n;
        for (Edge edge : graph.get(source)) {
            if (edge.residual == 0) continue;
            long amount = edge.residual;
            edge.residual = 0;
            Edge reverse = graph.get(edge.to).get(edge.rev);
            reverse.residual = Math.addExact(reverse.residual, amount);
            excess[source] = Math.subtractExact(excess[source], amount);
            excess[edge.to] = Math.addExact(excess[edge.to], amount);
            activate(edge.to, source, sink, excess, queued, active);
        }

        while (!active.isEmpty()) {
            int u = active.remove();
            queued[u] = false;
            discharge(u, source, sink, height, nextEdge, excess, queued, active);
            activate(u, source, sink, excess, queued, active);
        }
        return excess[sink];
    }

    private static void activate(int v, int source, int sink, long[] excess,
                                 boolean[] queued, ArrayDeque<Integer> active) {
        if (v != source && v != sink && excess[v] > 0 && !queued[v]) {
            queued[v] = true;
            active.add(v);
        }
    }

    private void discharge(int u, int source, int sink, int[] height,
                           int[] nextEdge, long[] excess, boolean[] queued,
                           ArrayDeque<Integer> active) {
        while (excess[u] > 0) {
            if (nextEdge[u] == graph.get(u).size()) {
                int minimum = Integer.MAX_VALUE;
                for (Edge edge : graph.get(u)) {
                    if (edge.residual > 0) minimum = Math.min(minimum, height[edge.to]);
                }
                if (minimum == Integer.MAX_VALUE) throw new IllegalStateException("no residual edge");
                height[u] = minimum + 1;
                nextEdge[u] = 0;
                continue;
            }
            Edge edge = graph.get(u).get(nextEdge[u]);
            if (edge.residual > 0 && height[u] == height[edge.to] + 1) {
                long amount = Math.min(excess[u], edge.residual);
                edge.residual -= amount;
                Edge reverse = graph.get(edge.to).get(edge.rev);
                reverse.residual = Math.addExact(reverse.residual, amount);
                excess[u] -= amount;
                excess[edge.to] = Math.addExact(excess[edge.to], amount);
                activate(edge.to, source, sink, excess, queued, active);
            } else {
                nextEdge[u]++;
            }
        }
    }

    public static void main(String[] args) {
        PushRelabel flow = new PushRelabel(6);
        long[][] edges = {
            {0,1,16}, {0,2,13}, {1,2,10}, {2,1,4}, {1,3,12},
            {2,4,14}, {3,2,9}, {4,3,7}, {3,5,20}, {4,5,4}
        };
        for (long[] edge : edges) flow.addEdge((int) edge[0], (int) edge[1], edge[2]);
        if (flow.maxFlow(0, 5) != 23L) throw new AssertionError();
    }
}

⚡ Complexity Analysis

Time Complexity

•
O(V² E) generic bound
Applies to arbitrary valid sequences of push and relabel operations
•
O(V³) for FIFO / relabel-to-front
The implementation above uses a FIFO active queue
•
At most O(V²) relabel operations
Each vertex relabeled at most 2V times
•
At most O(V E) saturating pushes
Each edge saturated at most V times

Space Complexity

•
O(V + E)
Paired residual adjacency lists and algorithm state
•
O(V) auxiliary
For height and excess arrays

💡 Pro Tip: Selection Strategies Matter!

The order in which you process vertices with excess significantly affects performance:

• FIFO: Process in queue order - O(V³) time
• Highest Label: Process highest vertex first - O(V² √E) time
• Lowest Label: Process lowest vertex first - also works well

FIFO is a clean baseline. Highest-label is often effective, but no policy wins universally; topology and heuristic frequency matter.

Heuristics used in serious implementations

Highest label

Discharge the active vertex with greatest height. The classic selection rule has a stronger O(V²√E) bound and often returns excess toward the source quickly.

Gap relabeling

If no vertex has height k, vertices above k and below V cannot reach the sink. Raise them to at least V+1 so stranded excess heads back to the source.

Global relabeling

Periodically run reverse BFS from the sink and reset labels to exact residual distances. It costs O(E), so trigger after a work budget rather than after every push.

Production review checklist

• Track current-arc indices so a discharge does not rescan dead edges.
• Queue a vertex only on the transition from zero to positive excess.
• Keep parallel and antiparallel edges as distinct reverse-indexed pairs.
• Reject self-loops in this API and reject source == sink.
• Use Java long; detect overflow when accumulating excess.
• Treat the residual structure as one-shot or rebuild it before a second query.

Test: verify capacity, final conservation, non-negative internal excess during the run, label validity on every residual edge, and equality between sink excess and the extracted minimum-cut capacity.

✅ Pros & ❌ Cons

✅ Advantages

✓Often fastest in practice for large dense graphs
✓Highly parallelizable (local operations)
✓No need to find augmenting paths
✓Works well with different selection strategies
✓Excellent for very large networks

❌ Limitations

✗More complex to implement correctly
✗Harder to understand conceptually
✗Can be slower than Dinic's for sparse graphs
✗Requires careful tuning for best performance
✗Not beginner-friendly

💼 Real World Applications

🏭 Industrial Optimization

Manufacturing plants use Push-Relabel for optimizing material flow through production lines, maximizing throughput while respecting machine capacities.

Example: Assembly line optimization

🌐 Large-Scale Networks

Tech giants use Push-Relabel variants for optimizing data flow in massive distributed systems and cloud infrastructure.

Example: Google's network optimization

🎬 Computer Vision

Image segmentation and object recognition use max flow/min cut, often implemented with Push-Relabel for speed.

Example: Background removal in photos

⚡ Power Grids

Electrical utilities use Push-Relabel for optimizing power distribution across transmission networks during peak demand.

Example: Smart grid load balancing

💼 Real World Application: Google's Infrastructure

Google has used variants of Push-Relabel in their infrastructure for network flow optimization. The algorithm's ability to work locally (without global path finding) makes it perfect for distributed systems where different parts of the network can process flow independently and in parallel!

Short takeaway

Push-relabel maintains a preflow and height labels: push excess downhill, relabel when stuck. At termination, excess remains only at s and t and the flow is maximum.

Exercises

Why may intermediate push-relabel states violate flow conservation, and what quantity tracks that violation?
State the height invariant on residual edges. What goes wrong if you push when h(u) ≠ h(v)+1?
Name two heuristics that make push-relabel fast in practice and what each roughly does.

Primary sources

Goldberg, A. V. & Tarjan, R. E.: A new approach to the maximum-flow problem (push-relabel).
Cormen et al., CLRS: Preflow-push algorithms.
Cherkassky & Goldberg: On implementing push-relabel method heuristics.