39.06Intermediate / Advanced5 topics17 min5 interactive animations

Push-relabel overview

Push-relabel never builds augmenting paths. It floods the source's neighbours, lets every vertex push its excess downhill along residual arcs, and raises a vertex only when it is stuck.

Learning goals

Explain excess, height and the preflow
Perform push and relabel steps and know when each applies
Run the generic algorithm on a small network
Describe the gap heuristic

Prerequisites

Residual graphsDinic's algorithm

Imagine flooding a valley: pour too much water in at the top, then let each pool spill to a lower neighbour; where a pool has nowhere lower to spill, raise the whole pool's level until it can. Eventually the surplus reaches the sea (the sink) or flows back to the spring (the source).

39.06.1

Vertex excess

Augmenting-path algorithms keep a valid flow throughout. Push-relabel keeps a **preflow**: each vertex may receive more than it sends. The surplus is its **excess** excess[v] = inflow − outflow >= 0. A vertex with positive excess other than the source and the sink is called **active**.

The algorithm starts by saturating every edge out of the source, so the source's neighbours receive their capacity as excess. In the sample network these are 10 units at vertex 1 and 10 units at vertex 2 (the animation's first frames). When no vertex other than s and t has excess left, the preflow is an ordinary flow, and it is maximum.

The code builds the initial state and returns the excess array.

Java

1static int[] saturateSource(Net g, int s, int t, int[] height, Deque<Integer> active) {   // initial preflow; returns excess[]
2    int[] excess = new int[g.n];
3    height[s] = g.n;                                           // the source starts as high as possible
4    for (int id : g.adj[s]) {
5        int c = g.cap[id], v = g.to[id];
6        if (c == 0) continue;
7        g.cap[id] = 0; g.cap[id ^ 1] += c; excess[v] += c;     // saturate the arc out of the source
8        if (v != t && excess[v] == c) active.add(v);
9    }
10    return excess;
11}

Maximum flow: Ford-Fulkerson, Edmonds-Karp, Dinic, push-relabel

Interactive · edit the input

edge label: flow / capacity · 6 vertices · 9 edges

source

sink

Current path or vertexEdge carrying some flowSaturated edge (flow = capacity)Source side of the minimum cut

residual arcs u→v : remaining capacity

0→1:10

0→2:10

1→2:2

1→3:4

1→4:8

2→4:9

3→5:10

4→3:6

4→5:10

Setup

Every edge starts with flow 0, so every arc has its full capacity as residual capacity and every reverse arc has 0. Edmonds-Karp (BFS paths) looks for ways to send more from 0 to 5. The label on an edge is flow / capacity.

Step 1 / 11

Java

1static class Net {
2    final int n;
3    final List<Integer>[] adj;                         // adj[u]: ids of the arcs leaving u
4    final int[] to, cap;                               // arc k and arc k ^ 1 are each other's reverse
5    int arcs = 0;
6    @SuppressWarnings("unchecked")
7    Net(int n, int maxEdges) {
8        this.n = n; adj = new List[n]; to = new int[2 * maxEdges]; cap = new int[2 * maxEdges];
9        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
10    }
11    void addEdge(int u, int v, int c) {
12        to[arcs] = v; cap[arcs] = c; adj[u].add(arcs++);        // forward arc with the capacity
13        to[arcs] = u; cap[arcs] = 0; adj[v].add(arcs++);        // reverse arc: capacity 0 until flow is pushed
14    }
15}
16static int fordFulkerson(Net g, int s, int t) {
17    int flow = 0;
18    while (true) {
19        int pushed = dfs(g, s, t, Integer.MAX_VALUE, new boolean[g.n]);   // any augmenting path, found depth-first
20        if (pushed == 0) return flow;
21        flow += pushed;
22    }
23}
24static int dfs(Net g, int u, int t, int f, boolean[] seen) {
25    if (u == t) return f;
26    seen[u] = true;
27    for (int id : g.adj[u]) {
28        int v = g.to[id];
29        if (seen[v] || g.cap[id] == 0) continue;
30        int d = dfs(g, v, t, Math.min(f, g.cap[id]), seen);
31        if (d > 0) { g.cap[id] -= d; g.cap[id ^ 1] += d; return d; }  // use d units, open d units of reverse capacity
32    }
33    return 0;
34}
35static int edmondsKarp(Net g, int s, int t) {
36    int flow = 0;
37    while (true) {
38        int[] viaArc = new int[g.n];
39        Arrays.fill(viaArc, -1);
40        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
41        while (!queue.isEmpty() && viaArc[t] == -1) {                  // BFS: the path with fewest arcs
42            int u = queue.poll();
43            for (int id : g.adj[u]) {
44                int v = g.to[id];
45                if (v != s && viaArc[v] == -1 && g.cap[id] > 0) { viaArc[v] = id; queue.add(v); }
46            }
47        }
48        if (viaArc[t] == -1) return flow;
49        int bottleneck = Integer.MAX_VALUE;
50        for (int v = t; v != s; v = g.to[viaArc[v] ^ 1]) bottleneck = Math.min(bottleneck, g.cap[viaArc[v]]);
51        for (int v = t; v != s; v = g.to[viaArc[v] ^ 1]) { g.cap[viaArc[v]] -= bottleneck; g.cap[viaArc[v] ^ 1] += bottleneck; }
52        flow += bottleneck;
53    }
54}
55static int dinic(Net g, int s, int t) {
56    int flow = 0;
57    int[] level = new int[g.n];
58    while (levels(g, s, t, level)) {                                   // new level graph; stop when t is unreachable
59        int[] next = new int[g.n];                                     // next arc to try at each vertex
60        for (int f; (f = blocking(g, s, t, Integer.MAX_VALUE, level, next)) > 0; ) flow += f;
61    }
62    return flow;
63}
64static boolean levels(Net g, int s, int t, int[] level) {
65    Arrays.fill(level, -1);
66    level[s] = 0;
67    Deque<Integer> queue = new ArrayDeque<>(List.of(s));
68    while (!queue.isEmpty()) {
69        int u = queue.poll();
70        for (int id : g.adj[u]) if (g.cap[id] > 0 && level[g.to[id]] == -1) { level[g.to[id]] = level[u] + 1; queue.add(g.to[id]); }
71    }
72    return level[t] != -1;
73}
74static int blocking(Net g, int u, int t, int f, int[] level, int[] next) {
75    if (u == t) return f;
76    for (; next[u] < g.adj[u].size(); next[u]++) {
77        int id = g.adj[u].get(next[u]), v = g.to[id];
78        if (g.cap[id] == 0 || level[v] != level[u] + 1) continue;      // only arcs one level deeper
79        int d = blocking(g, v, t, Math.min(f, g.cap[id]), level, next);
80        if (d > 0) { g.cap[id] -= d; g.cap[id ^ 1] += d; return d; }
81    }
82    return 0;
83}
84static int pushRelabel(Net g, int s, int t) {
85    int[] height = new int[g.n], excess = new int[g.n];
86    height[s] = g.n;                                                   // the source starts as high as possible
87    Deque<Integer> active = new ArrayDeque<>();
88    for (int id : g.adj[s]) {                                          // saturate every arc out of the source
89        int c = g.cap[id], v = g.to[id];
90        if (c == 0) continue;
91        g.cap[id] = 0; g.cap[id ^ 1] += c; excess[v] += c;
92        if (v != t && excess[v] == c) active.add(v);
93    }
94    while (!active.isEmpty()) discharge(g, active.poll(), s, t, height, excess, active);
95    return excess[t];
96}
97static void discharge(Net g, int u, int s, int t, int[] height, int[] excess, Deque<Integer> active) {
98    while (excess[u] > 0) {
99        boolean pushed = false;
100        for (int id : g.adj[u]) {
101            int v = g.to[id];
102            if (g.cap[id] > 0 && height[u] == height[v] + 1) {         // push only downhill, by exactly one level
103                int d = Math.min(excess[u], g.cap[id]);
104                g.cap[id] -= d; g.cap[id ^ 1] += d; excess[u] -= d; excess[v] += d;
105                if (v != s && v != t && excess[v] == d) active.add(v);
106                pushed = true;
107                if (excess[u] == 0) break;
108            }
109        }
110        if (!pushed) {                                                 // stuck: relabel one above its lowest residual neighbour
111            int lowest = Integer.MAX_VALUE;
112            for (int id : g.adj[u]) if (g.cap[id] > 0) lowest = Math.min(lowest, height[g.to[id]]);
113            height[u] = lowest + 1;
114        }
115    }
116}

Live state

0 augmentations0 phases0 pushes0 relabels

edges

source

sink

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L16	n=6 edges=9 source=0 sink=5	Every edge starts with flow 0, so every arc has its full capacity as residual capacity and every reverse arc has 0. Edmonds-Karp (BFS paths) looks for ways to send more from 0 to 5. The label on an edge is flow / capacity.
2	L48	path=0→1→3→5 bottleneck=4 flow=0	Breadth-first search (fewest arcs) finds the path 0→1→3→5 with 3 arcs. Its smallest residual capacity is 4.
3	L51	bottleneck=4 flow=4	Push 4 along the path. Flow value is now 4.
4	L48	path=0→1→4→5 bottleneck=6 flow=4	Breadth-first search (fewest arcs) finds the path 0→1→4→5 with 3 arcs. Its smallest residual capacity is 6.
5	L51	bottleneck=6 flow=10	Push 6 along the path. Flow value is now 10.
6	L48	path=0→2→4→5 bottleneck=4 flow=10	Breadth-first search (fewest arcs) finds the path 0→2→4→5 with 3 arcs. Its smallest residual capacity is 4.
7	L51	bottleneck=4 flow=14	Push 4 along the path. Flow value is now 14.
8	L48	path=0→2→4→3→5 bottleneck=5 flow=14	Breadth-first search (fewest arcs) finds the path 0→2→4→3→5 with 4 arcs. Its smallest residual capacity is 5.
9	L51	bottleneck=5 flow=19	Push 5 along the path. Flow value is now 19.
10	L48	flow=19	No path with positive residual capacity from 0 to 5 remains: the search ends.
11	L16	return=19 cut_capacity=19 augmentations=4	Maximum flow = 19. The vertices still reachable from 0 in the residual graph, {0, 2}, form the minimum cut: the edges leaving that set (0→1, 2→4) are all saturated and their capacities add up to 19, the same number.

39.06.2

Height labels

Each vertex carries a **height** h[v], a guess at its distance from the sink. The source is fixed at height n and the sink at 0; everything else starts at 0. The labelling must be **valid**: for every residual arc u → v, h[u] <= h[v] + 1. A valid labelling means a vertex can only need to go down by one step at a time.

Validity has two consequences. Because the source is at height n, no residual path from s to t can exist (a path has at most n - 1 arcs and would have to descend from n to 0 by at most 1 per arc): so when no active vertex remains, the flow is maximum. And excess that cannot reach the sink eventually climbs above n and is sent back to the source, which is how the algorithm undoes overshoot.

The code checks validity; it holds after the initial saturation and is preserved by every push and relabel.

Java

1static boolean isValidLabeling(Net g, int s, int t, int[] height) {
2    if (height[s] != g.n || height[t] != 0) return false;
3    for (int u = 0; u < g.n; u++)
4        for (int id : g.adj[u])
5            if (g.cap[id] > 0 && height[u] > height[g.to[id]] + 1) return false;   // an arc may descend by one at most
6    return true;
7}

Maximum flow: Ford-Fulkerson, Edmonds-Karp, Dinic, push-relabel

Interactive · edit the input

edge label: flow / capacity · 6 vertices · 9 edges

source

sink

Current path or vertexEdge carrying some flowSaturated edge (flow = capacity)Source side of the minimum cut

residual arcs u→v : remaining capacity

0→1:10

0→2:10

1→2:2

1→3:4

1→4:8

2→4:9

3→5:10

4→3:6

4→5:10

Setup

Step 1 / 11

Java

1static class Net {
2    final int n;
3    final List<Integer>[] adj;                         // adj[u]: ids of the arcs leaving u
4    final int[] to, cap;                               // arc k and arc k ^ 1 are each other's reverse
5    int arcs = 0;
6    @SuppressWarnings("unchecked")
7    Net(int n, int maxEdges) {
8        this.n = n; adj = new List[n]; to = new int[2 * maxEdges]; cap = new int[2 * maxEdges];
9        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
10    }
11    void addEdge(int u, int v, int c) {
12        to[arcs] = v; cap[arcs] = c; adj[u].add(arcs++);        // forward arc with the capacity
13        to[arcs] = u; cap[arcs] = 0; adj[v].add(arcs++);        // reverse arc: capacity 0 until flow is pushed
14    }
15}
16static int fordFulkerson(Net g, int s, int t) {
17    int flow = 0;
18    while (true) {
19        int pushed = dfs(g, s, t, Integer.MAX_VALUE, new boolean[g.n]);   // any augmenting path, found depth-first
20        if (pushed == 0) return flow;
21        flow += pushed;
22    }
23}
24static int dfs(Net g, int u, int t, int f, boolean[] seen) {
25    if (u == t) return f;
26    seen[u] = true;
27    for (int id : g.adj[u]) {
28        int v = g.to[id];
29        if (seen[v] || g.cap[id] == 0) continue;
30        int d = dfs(g, v, t, Math.min(f, g.cap[id]), seen);
31        if (d > 0) { g.cap[id] -= d; g.cap[id ^ 1] += d; return d; }  // use d units, open d units of reverse capacity
32    }
33    return 0;
34}
35static int edmondsKarp(Net g, int s, int t) {
36    int flow = 0;
37    while (true) {
38        int[] viaArc = new int[g.n];
39        Arrays.fill(viaArc, -1);
40        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
41        while (!queue.isEmpty() && viaArc[t] == -1) {                  // BFS: the path with fewest arcs
42            int u = queue.poll();
43            for (int id : g.adj[u]) {
44                int v = g.to[id];
45                if (v != s && viaArc[v] == -1 && g.cap[id] > 0) { viaArc[v] = id; queue.add(v); }
46            }
47        }
48        if (viaArc[t] == -1) return flow;
49        int bottleneck = Integer.MAX_VALUE;
50        for (int v = t; v != s; v = g.to[viaArc[v] ^ 1]) bottleneck = Math.min(bottleneck, g.cap[viaArc[v]]);
51        for (int v = t; v != s; v = g.to[viaArc[v] ^ 1]) { g.cap[viaArc[v]] -= bottleneck; g.cap[viaArc[v] ^ 1] += bottleneck; }
52        flow += bottleneck;
53    }
54}
55static int dinic(Net g, int s, int t) {
56    int flow = 0;
57    int[] level = new int[g.n];
58    while (levels(g, s, t, level)) {                                   // new level graph; stop when t is unreachable
59        int[] next = new int[g.n];                                     // next arc to try at each vertex
60        for (int f; (f = blocking(g, s, t, Integer.MAX_VALUE, level, next)) > 0; ) flow += f;
61    }
62    return flow;
63}
64static boolean levels(Net g, int s, int t, int[] level) {
65    Arrays.fill(level, -1);
66    level[s] = 0;
67    Deque<Integer> queue = new ArrayDeque<>(List.of(s));
68    while (!queue.isEmpty()) {
69        int u = queue.poll();
70        for (int id : g.adj[u]) if (g.cap[id] > 0 && level[g.to[id]] == -1) { level[g.to[id]] = level[u] + 1; queue.add(g.to[id]); }
71    }
72    return level[t] != -1;
73}
74static int blocking(Net g, int u, int t, int f, int[] level, int[] next) {
75    if (u == t) return f;
76    for (; next[u] < g.adj[u].size(); next[u]++) {
77        int id = g.adj[u].get(next[u]), v = g.to[id];
78        if (g.cap[id] == 0 || level[v] != level[u] + 1) continue;      // only arcs one level deeper
79        int d = blocking(g, v, t, Math.min(f, g.cap[id]), level, next);
80        if (d > 0) { g.cap[id] -= d; g.cap[id ^ 1] += d; return d; }
81    }
82    return 0;
83}
84static int pushRelabel(Net g, int s, int t) {
85    int[] height = new int[g.n], excess = new int[g.n];
86    height[s] = g.n;                                                   // the source starts as high as possible
87    Deque<Integer> active = new ArrayDeque<>();
88    for (int id : g.adj[s]) {                                          // saturate every arc out of the source
89        int c = g.cap[id], v = g.to[id];
90        if (c == 0) continue;
91        g.cap[id] = 0; g.cap[id ^ 1] += c; excess[v] += c;
92        if (v != t && excess[v] == c) active.add(v);
93    }
94    while (!active.isEmpty()) discharge(g, active.poll(), s, t, height, excess, active);
95    return excess[t];
96}
97static void discharge(Net g, int u, int s, int t, int[] height, int[] excess, Deque<Integer> active) {
98    while (excess[u] > 0) {
99        boolean pushed = false;
100        for (int id : g.adj[u]) {
101            int v = g.to[id];
102            if (g.cap[id] > 0 && height[u] == height[v] + 1) {         // push only downhill, by exactly one level
103                int d = Math.min(excess[u], g.cap[id]);
104                g.cap[id] -= d; g.cap[id ^ 1] += d; excess[u] -= d; excess[v] += d;
105                if (v != s && v != t && excess[v] == d) active.add(v);
106                pushed = true;
107                if (excess[u] == 0) break;
108            }
109        }
110        if (!pushed) {                                                 // stuck: relabel one above its lowest residual neighbour
111            int lowest = Integer.MAX_VALUE;
112            for (int id : g.adj[u]) if (g.cap[id] > 0) lowest = Math.min(lowest, height[g.to[id]]);
113            height[u] = lowest + 1;
114        }
115    }
116}

Live state

0 augmentations0 phases0 pushes0 relabels

edges

source

sink

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L16	n=6 edges=9 source=0 sink=5	Every edge starts with flow 0, so every arc has its full capacity as residual capacity and every reverse arc has 0. Edmonds-Karp (BFS paths) looks for ways to send more from 0 to 5. The label on an edge is flow / capacity.
2	L48	path=0→1→3→5 bottleneck=4 flow=0	Breadth-first search (fewest arcs) finds the path 0→1→3→5 with 3 arcs. Its smallest residual capacity is 4.
3	L51	bottleneck=4 flow=4	Push 4 along the path. Flow value is now 4.
4	L48	path=0→1→4→5 bottleneck=6 flow=4	Breadth-first search (fewest arcs) finds the path 0→1→4→5 with 3 arcs. Its smallest residual capacity is 6.
5	L51	bottleneck=6 flow=10	Push 6 along the path. Flow value is now 10.
6	L48	path=0→2→4→5 bottleneck=4 flow=10	Breadth-first search (fewest arcs) finds the path 0→2→4→5 with 3 arcs. Its smallest residual capacity is 4.
7	L51	bottleneck=4 flow=14	Push 4 along the path. Flow value is now 14.
8	L48	path=0→2→4→3→5 bottleneck=5 flow=14	Breadth-first search (fewest arcs) finds the path 0→2→4→3→5 with 4 arcs. Its smallest residual capacity is 5.
9	L51	bottleneck=5 flow=19	Push 5 along the path. Flow value is now 19.
10	L48	flow=19	No path with positive residual capacity from 0 to 5 remains: the search ends.
11	L16	return=19 cut_capacity=19 augmentations=4	Maximum flow = 19. The vertices still reachable from 0 in the residual graph, {0, 2}, form the minimum cut: the edges leaving that set (0→1, 2→4) are all saturated and their capacities add up to 19, the same number.

39.06.3

Push

A **push** moves excess along a residual arc u → v when h[u] == h[v] + 1: from u exactly one level down. The amount is min(excess[u], cap). The arc shrinks, its reverse grows, excess[u] falls and excess[v] rises. A push is **saturating** if it uses the whole arc capacity, otherwise it empties the vertex's excess.

Pushes along reverse arcs are normal: they return flow that overshot. Watch the animation's log: a message ending “a reverse arc: this returns flow” marks one.

The code shows one push attempt; it returns the amount moved (0 if the arc is not eligible).

Java

1static int tryPush(Net g, int u, int id, int s, int t, int[] height, int[] excess, Deque<Integer> active) {
2    int v = g.to[id];
3    if (g.cap[id] == 0 || height[u] != height[v] + 1) return 0;        // only downhill by exactly one level
4    int d = Math.min(excess[u], g.cap[id]);
5    g.cap[id] -= d; g.cap[id ^ 1] += d;
6    excess[u] -= d; excess[v] += d;
7    if (v != s && v != t && excess[v] == d) active.add(v);             // v just became active
8    return d;
9}

Maximum flow: Ford-Fulkerson, Edmonds-Karp, Dinic, push-relabel

Interactive · edit the input

edge label: flow / capacity · 6 vertices · 9 edges

source

sink

Current path or vertexEdge carrying some flowSaturated edge (flow = capacity)Source side of the minimum cut

residual arcs u→v : remaining capacity

0→1:10

0→2:10

1→2:2

1→3:4

1→4:8

2→4:9

3→5:10

4→3:6

4→5:10

Setup

Step 1 / 11

Java

1static class Net {
2    final int n;
3    final List<Integer>[] adj;                         // adj[u]: ids of the arcs leaving u
4    final int[] to, cap;                               // arc k and arc k ^ 1 are each other's reverse
5    int arcs = 0;
6    @SuppressWarnings("unchecked")
7    Net(int n, int maxEdges) {
8        this.n = n; adj = new List[n]; to = new int[2 * maxEdges]; cap = new int[2 * maxEdges];
9        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
10    }
11    void addEdge(int u, int v, int c) {
12        to[arcs] = v; cap[arcs] = c; adj[u].add(arcs++);        // forward arc with the capacity
13        to[arcs] = u; cap[arcs] = 0; adj[v].add(arcs++);        // reverse arc: capacity 0 until flow is pushed
14    }
15}
16static int fordFulkerson(Net g, int s, int t) {
17    int flow = 0;
18    while (true) {
19        int pushed = dfs(g, s, t, Integer.MAX_VALUE, new boolean[g.n]);   // any augmenting path, found depth-first
20        if (pushed == 0) return flow;
21        flow += pushed;
22    }
23}
24static int dfs(Net g, int u, int t, int f, boolean[] seen) {
25    if (u == t) return f;
26    seen[u] = true;
27    for (int id : g.adj[u]) {
28        int v = g.to[id];
29        if (seen[v] || g.cap[id] == 0) continue;
30        int d = dfs(g, v, t, Math.min(f, g.cap[id]), seen);
31        if (d > 0) { g.cap[id] -= d; g.cap[id ^ 1] += d; return d; }  // use d units, open d units of reverse capacity
32    }
33    return 0;
34}
35static int edmondsKarp(Net g, int s, int t) {
36    int flow = 0;
37    while (true) {
38        int[] viaArc = new int[g.n];
39        Arrays.fill(viaArc, -1);
40        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
41        while (!queue.isEmpty() && viaArc[t] == -1) {                  // BFS: the path with fewest arcs
42            int u = queue.poll();
43            for (int id : g.adj[u]) {
44                int v = g.to[id];
45                if (v != s && viaArc[v] == -1 && g.cap[id] > 0) { viaArc[v] = id; queue.add(v); }
46            }
47        }
48        if (viaArc[t] == -1) return flow;
49        int bottleneck = Integer.MAX_VALUE;
50        for (int v = t; v != s; v = g.to[viaArc[v] ^ 1]) bottleneck = Math.min(bottleneck, g.cap[viaArc[v]]);
51        for (int v = t; v != s; v = g.to[viaArc[v] ^ 1]) { g.cap[viaArc[v]] -= bottleneck; g.cap[viaArc[v] ^ 1] += bottleneck; }
52        flow += bottleneck;
53    }
54}
55static int dinic(Net g, int s, int t) {
56    int flow = 0;
57    int[] level = new int[g.n];
58    while (levels(g, s, t, level)) {                                   // new level graph; stop when t is unreachable
59        int[] next = new int[g.n];                                     // next arc to try at each vertex
60        for (int f; (f = blocking(g, s, t, Integer.MAX_VALUE, level, next)) > 0; ) flow += f;
61    }
62    return flow;
63}
64static boolean levels(Net g, int s, int t, int[] level) {
65    Arrays.fill(level, -1);
66    level[s] = 0;
67    Deque<Integer> queue = new ArrayDeque<>(List.of(s));
68    while (!queue.isEmpty()) {
69        int u = queue.poll();
70        for (int id : g.adj[u]) if (g.cap[id] > 0 && level[g.to[id]] == -1) { level[g.to[id]] = level[u] + 1; queue.add(g.to[id]); }
71    }
72    return level[t] != -1;
73}
74static int blocking(Net g, int u, int t, int f, int[] level, int[] next) {
75    if (u == t) return f;
76    for (; next[u] < g.adj[u].size(); next[u]++) {
77        int id = g.adj[u].get(next[u]), v = g.to[id];
78        if (g.cap[id] == 0 || level[v] != level[u] + 1) continue;      // only arcs one level deeper
79        int d = blocking(g, v, t, Math.min(f, g.cap[id]), level, next);
80        if (d > 0) { g.cap[id] -= d; g.cap[id ^ 1] += d; return d; }
81    }
82    return 0;
83}
84static int pushRelabel(Net g, int s, int t) {
85    int[] height = new int[g.n], excess = new int[g.n];
86    height[s] = g.n;                                                   // the source starts as high as possible
87    Deque<Integer> active = new ArrayDeque<>();
88    for (int id : g.adj[s]) {                                          // saturate every arc out of the source
89        int c = g.cap[id], v = g.to[id];
90        if (c == 0) continue;
91        g.cap[id] = 0; g.cap[id ^ 1] += c; excess[v] += c;
92        if (v != t && excess[v] == c) active.add(v);
93    }
94    while (!active.isEmpty()) discharge(g, active.poll(), s, t, height, excess, active);
95    return excess[t];
96}
97static void discharge(Net g, int u, int s, int t, int[] height, int[] excess, Deque<Integer> active) {
98    while (excess[u] > 0) {
99        boolean pushed = false;
100        for (int id : g.adj[u]) {
101            int v = g.to[id];
102            if (g.cap[id] > 0 && height[u] == height[v] + 1) {         // push only downhill, by exactly one level
103                int d = Math.min(excess[u], g.cap[id]);
104                g.cap[id] -= d; g.cap[id ^ 1] += d; excess[u] -= d; excess[v] += d;
105                if (v != s && v != t && excess[v] == d) active.add(v);
106                pushed = true;
107                if (excess[u] == 0) break;
108            }
109        }
110        if (!pushed) {                                                 // stuck: relabel one above its lowest residual neighbour
111            int lowest = Integer.MAX_VALUE;
112            for (int id : g.adj[u]) if (g.cap[id] > 0) lowest = Math.min(lowest, height[g.to[id]]);
113            height[u] = lowest + 1;
114        }
115    }
116}

Live state

0 augmentations0 phases0 pushes0 relabels

edges

source

sink

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L16	n=6 edges=9 source=0 sink=5	Every edge starts with flow 0, so every arc has its full capacity as residual capacity and every reverse arc has 0. Edmonds-Karp (BFS paths) looks for ways to send more from 0 to 5. The label on an edge is flow / capacity.
2	L48	path=0→1→3→5 bottleneck=4 flow=0	Breadth-first search (fewest arcs) finds the path 0→1→3→5 with 3 arcs. Its smallest residual capacity is 4.
3	L51	bottleneck=4 flow=4	Push 4 along the path. Flow value is now 4.
4	L48	path=0→1→4→5 bottleneck=6 flow=4	Breadth-first search (fewest arcs) finds the path 0→1→4→5 with 3 arcs. Its smallest residual capacity is 6.
5	L51	bottleneck=6 flow=10	Push 6 along the path. Flow value is now 10.
6	L48	path=0→2→4→5 bottleneck=4 flow=10	Breadth-first search (fewest arcs) finds the path 0→2→4→5 with 3 arcs. Its smallest residual capacity is 4.
7	L51	bottleneck=4 flow=14	Push 4 along the path. Flow value is now 14.
8	L48	path=0→2→4→3→5 bottleneck=5 flow=14	Breadth-first search (fewest arcs) finds the path 0→2→4→3→5 with 4 arcs. Its smallest residual capacity is 5.
9	L51	bottleneck=5 flow=19	Push 5 along the path. Flow value is now 19.
10	L48	flow=19	No path with positive residual capacity from 0 to 5 remains: the search ends.
11	L16	return=19 cut_capacity=19 augmentations=4	Maximum flow = 19. The vertices still reachable from 0 in the residual graph, {0, 2}, form the minimum cut: the edges leaving that set (0→1, 2→4) are all saturated and their capacities add up to 19, the same number.

39.06.4

Relabel

A vertex with excess but no eligible arc is stuck: all of its residual arcs lead to vertices at the same height or higher. **Relabel** raises it to one more than its lowest residual neighbour, h[u] = 1 + min h[v], which is the smallest increase that makes some arc eligible. Heights only ever increase, and each vertex is relabelled fewer than 2n times, which bounds the whole algorithm.

Try the “Push-relabel on the same network” preset: it ends with 14 pushes and 8 relabels on the 6-vertex sample network, with flow 19. In the animation each relabel frame explains which neighbour the vertex climbed over.

Every relabel keeps the labelling valid because the new height is exactly one above the lowest residual neighbour.

Java

1static void relabel(Net g, int u, int[] height) {
2    int lowest = Integer.MAX_VALUE;
3    for (int id : g.adj[u]) if (g.cap[id] > 0) lowest = Math.min(lowest, height[g.to[id]]);
4    height[u] = lowest + 1;                                            // one above the lowest vertex it can still push to
5}

Worst

O(V² · E) for generic push-relabel, O(V³) for the FIFO order

Space

O(V + E)

Maximum flow: Ford-Fulkerson, Edmonds-Karp, Dinic, push-relabel

Interactive · edit the input

edge label: flow / capacity · 6 vertices · 9 edges

source

sink

Current path or vertexEdge carrying some flowSaturated edge (flow = capacity)Source side of the minimum cut

residual arcs u→v : remaining capacity

0→1:10

0→2:10

1→2:2

1→3:4

1→4:8

2→4:9

3→5:10

4→3:6

4→5:10

Setup

Step 1 / 11

Java

1static class Net {
2    final int n;
3    final List<Integer>[] adj;                         // adj[u]: ids of the arcs leaving u
4    final int[] to, cap;                               // arc k and arc k ^ 1 are each other's reverse
5    int arcs = 0;
6    @SuppressWarnings("unchecked")
7    Net(int n, int maxEdges) {
8        this.n = n; adj = new List[n]; to = new int[2 * maxEdges]; cap = new int[2 * maxEdges];
9        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
10    }
11    void addEdge(int u, int v, int c) {
12        to[arcs] = v; cap[arcs] = c; adj[u].add(arcs++);        // forward arc with the capacity
13        to[arcs] = u; cap[arcs] = 0; adj[v].add(arcs++);        // reverse arc: capacity 0 until flow is pushed
14    }
15}
16static int fordFulkerson(Net g, int s, int t) {
17    int flow = 0;
18    while (true) {
19        int pushed = dfs(g, s, t, Integer.MAX_VALUE, new boolean[g.n]);   // any augmenting path, found depth-first
20        if (pushed == 0) return flow;
21        flow += pushed;
22    }
23}
24static int dfs(Net g, int u, int t, int f, boolean[] seen) {
25    if (u == t) return f;
26    seen[u] = true;
27    for (int id : g.adj[u]) {
28        int v = g.to[id];
29        if (seen[v] || g.cap[id] == 0) continue;
30        int d = dfs(g, v, t, Math.min(f, g.cap[id]), seen);
31        if (d > 0) { g.cap[id] -= d; g.cap[id ^ 1] += d; return d; }  // use d units, open d units of reverse capacity
32    }
33    return 0;
34}
35static int edmondsKarp(Net g, int s, int t) {
36    int flow = 0;
37    while (true) {
38        int[] viaArc = new int[g.n];
39        Arrays.fill(viaArc, -1);
40        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
41        while (!queue.isEmpty() && viaArc[t] == -1) {                  // BFS: the path with fewest arcs
42            int u = queue.poll();
43            for (int id : g.adj[u]) {
44                int v = g.to[id];
45                if (v != s && viaArc[v] == -1 && g.cap[id] > 0) { viaArc[v] = id; queue.add(v); }
46            }
47        }
48        if (viaArc[t] == -1) return flow;
49        int bottleneck = Integer.MAX_VALUE;
50        for (int v = t; v != s; v = g.to[viaArc[v] ^ 1]) bottleneck = Math.min(bottleneck, g.cap[viaArc[v]]);
51        for (int v = t; v != s; v = g.to[viaArc[v] ^ 1]) { g.cap[viaArc[v]] -= bottleneck; g.cap[viaArc[v] ^ 1] += bottleneck; }
52        flow += bottleneck;
53    }
54}
55static int dinic(Net g, int s, int t) {
56    int flow = 0;
57    int[] level = new int[g.n];
58    while (levels(g, s, t, level)) {                                   // new level graph; stop when t is unreachable
59        int[] next = new int[g.n];                                     // next arc to try at each vertex
60        for (int f; (f = blocking(g, s, t, Integer.MAX_VALUE, level, next)) > 0; ) flow += f;
61    }
62    return flow;
63}
64static boolean levels(Net g, int s, int t, int[] level) {
65    Arrays.fill(level, -1);
66    level[s] = 0;
67    Deque<Integer> queue = new ArrayDeque<>(List.of(s));
68    while (!queue.isEmpty()) {
69        int u = queue.poll();
70        for (int id : g.adj[u]) if (g.cap[id] > 0 && level[g.to[id]] == -1) { level[g.to[id]] = level[u] + 1; queue.add(g.to[id]); }
71    }
72    return level[t] != -1;
73}
74static int blocking(Net g, int u, int t, int f, int[] level, int[] next) {
75    if (u == t) return f;
76    for (; next[u] < g.adj[u].size(); next[u]++) {
77        int id = g.adj[u].get(next[u]), v = g.to[id];
78        if (g.cap[id] == 0 || level[v] != level[u] + 1) continue;      // only arcs one level deeper
79        int d = blocking(g, v, t, Math.min(f, g.cap[id]), level, next);
80        if (d > 0) { g.cap[id] -= d; g.cap[id ^ 1] += d; return d; }
81    }
82    return 0;
83}
84static int pushRelabel(Net g, int s, int t) {
85    int[] height = new int[g.n], excess = new int[g.n];
86    height[s] = g.n;                                                   // the source starts as high as possible
87    Deque<Integer> active = new ArrayDeque<>();
88    for (int id : g.adj[s]) {                                          // saturate every arc out of the source
89        int c = g.cap[id], v = g.to[id];
90        if (c == 0) continue;
91        g.cap[id] = 0; g.cap[id ^ 1] += c; excess[v] += c;
92        if (v != t && excess[v] == c) active.add(v);
93    }
94    while (!active.isEmpty()) discharge(g, active.poll(), s, t, height, excess, active);
95    return excess[t];
96}
97static void discharge(Net g, int u, int s, int t, int[] height, int[] excess, Deque<Integer> active) {
98    while (excess[u] > 0) {
99        boolean pushed = false;
100        for (int id : g.adj[u]) {
101            int v = g.to[id];
102            if (g.cap[id] > 0 && height[u] == height[v] + 1) {         // push only downhill, by exactly one level
103                int d = Math.min(excess[u], g.cap[id]);
104                g.cap[id] -= d; g.cap[id ^ 1] += d; excess[u] -= d; excess[v] += d;
105                if (v != s && v != t && excess[v] == d) active.add(v);
106                pushed = true;
107                if (excess[u] == 0) break;
108            }
109        }
110        if (!pushed) {                                                 // stuck: relabel one above its lowest residual neighbour
111            int lowest = Integer.MAX_VALUE;
112            for (int id : g.adj[u]) if (g.cap[id] > 0) lowest = Math.min(lowest, height[g.to[id]]);
113            height[u] = lowest + 1;
114        }
115    }
116}

Live state

0 augmentations0 phases0 pushes0 relabels

edges

source

sink

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L16	n=6 edges=9 source=0 sink=5	Every edge starts with flow 0, so every arc has its full capacity as residual capacity and every reverse arc has 0. Edmonds-Karp (BFS paths) looks for ways to send more from 0 to 5. The label on an edge is flow / capacity.
2	L48	path=0→1→3→5 bottleneck=4 flow=0	Breadth-first search (fewest arcs) finds the path 0→1→3→5 with 3 arcs. Its smallest residual capacity is 4.
3	L51	bottleneck=4 flow=4	Push 4 along the path. Flow value is now 4.
4	L48	path=0→1→4→5 bottleneck=6 flow=4	Breadth-first search (fewest arcs) finds the path 0→1→4→5 with 3 arcs. Its smallest residual capacity is 6.
5	L51	bottleneck=6 flow=10	Push 6 along the path. Flow value is now 10.
6	L48	path=0→2→4→5 bottleneck=4 flow=10	Breadth-first search (fewest arcs) finds the path 0→2→4→5 with 3 arcs. Its smallest residual capacity is 4.
7	L51	bottleneck=4 flow=14	Push 4 along the path. Flow value is now 14.
8	L48	path=0→2→4→3→5 bottleneck=5 flow=14	Breadth-first search (fewest arcs) finds the path 0→2→4→3→5 with 4 arcs. Its smallest residual capacity is 5.
9	L51	bottleneck=5 flow=19	Push 5 along the path. Flow value is now 19.
10	L48	flow=19	No path with positive residual capacity from 0 to 5 remains: the search ends.
11	L16	return=19 cut_capacity=19 augmentations=4	Maximum flow = 19. The vertices still reachable from 0 in the residual graph, {0, 2}, form the minimum cut: the edges leaving that set (0→1, 2→4) are all saturated and their capacities add up to 19, the same number.

39.06.5

Gap heuristic

Practical push-relabel codes add heuristics. The **gap heuristic**: if after a relabel no vertex has height h for some 0 < h < n, then no vertex above h can reach the sink (a path would have to step through every height). Lift all vertices with height strictly between h and n to n + 1, so their excess goes back to the source immediately instead of crawling up one level at a time.

The method below is complete push-relabel with the FIFO active queue and the gap rule. It returns the same flow as the plain version; it only saves relabel steps. A related heuristic is **global relabelling**: recompute exact heights with a backward BFS from the sink every so often.

The correctness of all of this rests on the invariant from the height-labels item: validity of the labelling at every moment.

Java

1static int pushRelabelGap(Net g, int s, int t) {
2    int n = g.n;
3    int[] height = new int[n];
4    Deque<Integer> active = new ArrayDeque<>();
5    int[] excess = saturateSource(g, s, t, height, active);
6    int[] count = new int[2 * n + 1];                                 // how many vertices have each height
7    for (int v = 0; v < n; v++) count[height[v]]++;
8    while (!active.isEmpty()) {
9        int u = active.poll();
10        while (excess[u] > 0) {
11            boolean pushed = false;
12            for (int id : g.adj[u]) {
13                if (tryPush(g, u, id, s, t, height, excess, active) > 0) {
14                    pushed = true;
15                    if (excess[u] == 0) break;
16                }
17            }
18            if (pushed) continue;
19            int old = height[u];
20            count[old]--;
21            relabel(g, u, height);
22            count[height[u]]++;
23            if (count[old] == 0 && old < n) {                          // a gap: nothing above it can reach the sink
24                for (int v = 0; v < n; v++) {
25                    if (v != s && height[v] > old && height[v] < n) { count[height[v]]--; height[v] = n + 1; count[n + 1]++; }
26                }
27            }
28        }
29    }
30    return excess[t];
31}

Maximum flow: Ford-Fulkerson, Edmonds-Karp, Dinic, push-relabel

Interactive · edit the input

edge label: flow / capacity · 6 vertices · 9 edges

source

sink

Current path or vertexEdge carrying some flowSaturated edge (flow = capacity)Source side of the minimum cut

residual arcs u→v : remaining capacity

0→1:10

0→2:10

1→2:2

1→3:4

1→4:8

2→4:9

3→5:10

4→3:6

4→5:10

Setup

Step 1 / 11

Java

1static class Net {
2    final int n;
3    final List<Integer>[] adj;                         // adj[u]: ids of the arcs leaving u
4    final int[] to, cap;                               // arc k and arc k ^ 1 are each other's reverse
5    int arcs = 0;
6    @SuppressWarnings("unchecked")
7    Net(int n, int maxEdges) {
8        this.n = n; adj = new List[n]; to = new int[2 * maxEdges]; cap = new int[2 * maxEdges];
9        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
10    }
11    void addEdge(int u, int v, int c) {
12        to[arcs] = v; cap[arcs] = c; adj[u].add(arcs++);        // forward arc with the capacity
13        to[arcs] = u; cap[arcs] = 0; adj[v].add(arcs++);        // reverse arc: capacity 0 until flow is pushed
14    }
15}
16static int fordFulkerson(Net g, int s, int t) {
17    int flow = 0;
18    while (true) {
19        int pushed = dfs(g, s, t, Integer.MAX_VALUE, new boolean[g.n]);   // any augmenting path, found depth-first
20        if (pushed == 0) return flow;
21        flow += pushed;
22    }
23}
24static int dfs(Net g, int u, int t, int f, boolean[] seen) {
25    if (u == t) return f;
26    seen[u] = true;
27    for (int id : g.adj[u]) {
28        int v = g.to[id];
29        if (seen[v] || g.cap[id] == 0) continue;
30        int d = dfs(g, v, t, Math.min(f, g.cap[id]), seen);
31        if (d > 0) { g.cap[id] -= d; g.cap[id ^ 1] += d; return d; }  // use d units, open d units of reverse capacity
32    }
33    return 0;
34}
35static int edmondsKarp(Net g, int s, int t) {
36    int flow = 0;
37    while (true) {
38        int[] viaArc = new int[g.n];
39        Arrays.fill(viaArc, -1);
40        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
41        while (!queue.isEmpty() && viaArc[t] == -1) {                  // BFS: the path with fewest arcs
42            int u = queue.poll();
43            for (int id : g.adj[u]) {
44                int v = g.to[id];
45                if (v != s && viaArc[v] == -1 && g.cap[id] > 0) { viaArc[v] = id; queue.add(v); }
46            }
47        }
48        if (viaArc[t] == -1) return flow;
49        int bottleneck = Integer.MAX_VALUE;
50        for (int v = t; v != s; v = g.to[viaArc[v] ^ 1]) bottleneck = Math.min(bottleneck, g.cap[viaArc[v]]);
51        for (int v = t; v != s; v = g.to[viaArc[v] ^ 1]) { g.cap[viaArc[v]] -= bottleneck; g.cap[viaArc[v] ^ 1] += bottleneck; }
52        flow += bottleneck;
53    }
54}
55static int dinic(Net g, int s, int t) {
56    int flow = 0;
57    int[] level = new int[g.n];
58    while (levels(g, s, t, level)) {                                   // new level graph; stop when t is unreachable
59        int[] next = new int[g.n];                                     // next arc to try at each vertex
60        for (int f; (f = blocking(g, s, t, Integer.MAX_VALUE, level, next)) > 0; ) flow += f;
61    }
62    return flow;
63}
64static boolean levels(Net g, int s, int t, int[] level) {
65    Arrays.fill(level, -1);
66    level[s] = 0;
67    Deque<Integer> queue = new ArrayDeque<>(List.of(s));
68    while (!queue.isEmpty()) {
69        int u = queue.poll();
70        for (int id : g.adj[u]) if (g.cap[id] > 0 && level[g.to[id]] == -1) { level[g.to[id]] = level[u] + 1; queue.add(g.to[id]); }
71    }
72    return level[t] != -1;
73}
74static int blocking(Net g, int u, int t, int f, int[] level, int[] next) {
75    if (u == t) return f;
76    for (; next[u] < g.adj[u].size(); next[u]++) {
77        int id = g.adj[u].get(next[u]), v = g.to[id];
78        if (g.cap[id] == 0 || level[v] != level[u] + 1) continue;      // only arcs one level deeper
79        int d = blocking(g, v, t, Math.min(f, g.cap[id]), level, next);
80        if (d > 0) { g.cap[id] -= d; g.cap[id ^ 1] += d; return d; }
81    }
82    return 0;
83}
84static int pushRelabel(Net g, int s, int t) {
85    int[] height = new int[g.n], excess = new int[g.n];
86    height[s] = g.n;                                                   // the source starts as high as possible
87    Deque<Integer> active = new ArrayDeque<>();
88    for (int id : g.adj[s]) {                                          // saturate every arc out of the source
89        int c = g.cap[id], v = g.to[id];
90        if (c == 0) continue;
91        g.cap[id] = 0; g.cap[id ^ 1] += c; excess[v] += c;
92        if (v != t && excess[v] == c) active.add(v);
93    }
94    while (!active.isEmpty()) discharge(g, active.poll(), s, t, height, excess, active);
95    return excess[t];
96}
97static void discharge(Net g, int u, int s, int t, int[] height, int[] excess, Deque<Integer> active) {
98    while (excess[u] > 0) {
99        boolean pushed = false;
100        for (int id : g.adj[u]) {
101            int v = g.to[id];
102            if (g.cap[id] > 0 && height[u] == height[v] + 1) {         // push only downhill, by exactly one level
103                int d = Math.min(excess[u], g.cap[id]);
104                g.cap[id] -= d; g.cap[id ^ 1] += d; excess[u] -= d; excess[v] += d;
105                if (v != s && v != t && excess[v] == d) active.add(v);
106                pushed = true;
107                if (excess[u] == 0) break;
108            }
109        }
110        if (!pushed) {                                                 // stuck: relabel one above its lowest residual neighbour
111            int lowest = Integer.MAX_VALUE;
112            for (int id : g.adj[u]) if (g.cap[id] > 0) lowest = Math.min(lowest, height[g.to[id]]);
113            height[u] = lowest + 1;
114        }
115    }
116}

Live state

0 augmentations0 phases0 pushes0 relabels

edges

source

sink

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L16	n=6 edges=9 source=0 sink=5	Every edge starts with flow 0, so every arc has its full capacity as residual capacity and every reverse arc has 0. Edmonds-Karp (BFS paths) looks for ways to send more from 0 to 5. The label on an edge is flow / capacity.
2	L48	path=0→1→3→5 bottleneck=4 flow=0	Breadth-first search (fewest arcs) finds the path 0→1→3→5 with 3 arcs. Its smallest residual capacity is 4.
3	L51	bottleneck=4 flow=4	Push 4 along the path. Flow value is now 4.
4	L48	path=0→1→4→5 bottleneck=6 flow=4	Breadth-first search (fewest arcs) finds the path 0→1→4→5 with 3 arcs. Its smallest residual capacity is 6.
5	L51	bottleneck=6 flow=10	Push 6 along the path. Flow value is now 10.
6	L48	path=0→2→4→5 bottleneck=4 flow=10	Breadth-first search (fewest arcs) finds the path 0→2→4→5 with 3 arcs. Its smallest residual capacity is 4.
7	L51	bottleneck=4 flow=14	Push 4 along the path. Flow value is now 14.
8	L48	path=0→2→4→3→5 bottleneck=5 flow=14	Breadth-first search (fewest arcs) finds the path 0→2→4→3→5 with 4 arcs. Its smallest residual capacity is 5.
9	L51	bottleneck=5 flow=19	Push 5 along the path. Flow value is now 19.
10	L48	flow=19	No path with positive residual capacity from 0 to 5 remains: the search ends.
11	L16	return=19 cut_capacity=19 augmentations=4	Maximum flow = 19. The vertices still reachable from 0 in the residual graph, {0, 2}, form the minimum cut: the edges leaving that set (0→1, 2→4) are all saturated and their capacities add up to 19, the same number.

Practice ladder

Now try it yourself

Easy

Find Center of Star Graph

Medium

Network Delay Time
Cheapest Flights Within K Stops

Advanced

Maximum Students Taking Exam
Distribute Repeating Integers

Key takeaways

Push-relabel keeps a preflow: vertices may hold excess that must be pushed on.
Push along a residual arc exactly one level downhill; relabel a stuck vertex to one above its lowest residual neighbour.
Heights only increase; the gap heuristic lifts vertices that can no longer reach the sink.