39.05Intermediate / Advanced5 topics17 min4 interactive animations

Dinic's algorithm

Dinic's algorithm works in phases. Each phase builds a BFS level graph and then pushes a blocking flow through it with a DFS that remembers dead ends; the sink distance grows every phase, so there are at most V phases.

Learning goals

Build a level graph from the residual graph
Compute a blocking flow with a current-arc pointer
Explain why there are at most V phases
Know the bounds for unit-capacity networks

Prerequisites

Edmonds-KarpBFS levels

Edmonds-Karp runs one BFS per path. Dinic runs one BFS and then reuses its map of distances to send many paths before searching again, like surveying the roads once and then driving many trucks along downhill routes.

39.05.1

Level graph

Run a BFS from the source over arcs with positive residual capacity and record the distance level[v] of each vertex. The **level graph** keeps only arcs that go from level i to level i + 1. Every source-sink path inside it is a shortest residual path.

Load the “Dinic on the same network” preset. Phase 1 reports that the sink is at level 3, and the animation's *level of each vertex* row shows the levels. The BFS also tells you when to stop: if the sink is unreachable (level[t] == -1) the flow is maximum.

Arcs that stay in the same level or go backwards are ignored in this phase even though they have capacity.

Java

1static boolean levels(Net g, int s, int t, int[] level) {
2    Arrays.fill(level, -1);
3    level[s] = 0;
4    Deque<Integer> queue = new ArrayDeque<>(List.of(s));
5    while (!queue.isEmpty()) {
6        int u = queue.poll();
7        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]); }
8    }
9    return level[t] != -1;                                          // false: no augmenting path, the flow is maximum
10}

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.05.2

Blocking flow

A **blocking flow** in the level graph is a flow that saturates at least one arc on every source-sink path of the level graph, so no further path exists there. It is not necessarily a maximum flow of the whole network; it only blocks this phase's shortest paths.

Compute it with DFS that only follows arcs one level deeper. The DFS keeps a pointer next[u] to the first arc at u that might still work. When an arc is saturated or leads to a dead end, the pointer moves past it and never comes back in this phase. That is what makes a whole phase cost O(V · E): each arc is skipped at most once per vertex and each successful path costs O(V).

In the sample phase 1 the animation finds three paths: 0→1→3→5 with 4 units, 0→1→4→5 with 6 units and 0→2→4→5 with 4 units, pushing the flow to 14 before the phase ends.

Java

1static int blocking(Net g, int u, int t, int f, int[] level, int[] next) {
2    if (u == t) return f;
3    for (; next[u] < g.adj[u].size(); next[u]++) {                  // next[u]: first arc at u that may still work
4        int id = g.adj[u].get(next[u]), v = g.to[id];
5        if (g.cap[id] == 0 || level[v] != level[u] + 1) continue;      // only arcs one level deeper
6        int d = blocking(g, v, t, Math.min(f, g.cap[id]), level, next);
7        if (d > 0) { g.cap[id] -= d; g.cap[id ^ 1] += d; return d; }
8    }
9    return 0;                                                       // dead end: every arc at u was tried
10}

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.05.3

DFS augmentation

The full algorithm alternates the two steps. Phase: BFS to get levels; if the sink is unreachable stop; otherwise reset next and call the blocking DFS repeatedly from the source until it returns 0, adding each pushed amount to the flow.

After a phase the residual graph has no shortest path of the old length left, so the next BFS gives a strictly larger sink distance. The sample network needs two phases: levels 3 and then 4. The second phase finds one more path, 0→2→4→3→5, which has 4 arcs, longer than any path the first phase could use, and pushes 5 units to reach 19.

Each phase costs O(V · E) and the sink distance, which is at most V − 1, grows every phase, so the total is O(V² · E).

Java

1static int dinic(Net g, int s, int t) {
2    int flow = 0;
3    int[] level = new int[g.n];
4    while (levels(g, s, t, level)) {                                // a new level graph; stop when t is unreachable
5        int[] next = new int[g.n];                                  // fresh arc pointers for the phase
6        for (int f; (f = blocking(g, s, t, Integer.MAX_VALUE, level, next)) > 0; ) flow += f;
7    }
8    return flow;
9}

Worst

O(V² · E)

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.05.4

Complexity

General networks: at most V − 1 phases (the sink distance grows each phase) and O(V · E) per phase gives O(V² · E). In practice Dinic is far faster than the bound, because phases are few and each blocking flow finds many paths at once.

For comparison on a graph with V vertices and E edges:

Algorithm	Time	Depends on capacities?
Ford-Fulkerson (DFS)	O(E · \|f\|)	yes
Edmonds-Karp	O(V · E²)	no
Dinic	O(V² · E)	no
Dinic, unit capacities	O(E · min(V^(2/3), E^(1/2)))	no
Push-relabel (FIFO)	O(V³)	no

39.05.5

Unit capacity variations

When every edge has capacity 1 (or, more generally, every vertex has a single incoming or outgoing unit edge), Dinic is much faster: each phase is O(E) and there are only O(√E) phases for unit networks, O(√V) for bipartite matching networks. This is the source of the Hopcroft-Karp bound in Chapter 40.

The code builds the standard matching network: a source joined to every left vertex, every allowed pair as a unit edge, and every right vertex joined to a sink, then runs Dinic. The maximum flow is the size of a maximum matching.

Load the “Dinic on the same network” preset and then set every capacity to 1 in the editor: the phases become short, and the number of augmentations equals the final flow.

Java

1static int maxMatching(int left, int right, int[][] pairs) {   // pairs {leftIndex, rightIndex}
2    int s = 0, t = left + right + 1;
3    Net g = new Net(t + 1, left + right + pairs.length);
4    for (int i = 0; i < left; i++) g.addEdge(s, 1 + i, 1);
5    for (int j = 0; j < right; j++) g.addEdge(1 + left + j, t, 1);
6    for (int[] p : pairs) g.addEdge(1 + p[0], 1 + left + p[1], 1);
7    return dinic(g, s, t);
8}

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

Number of Provinces
Is Graph Bipartite?

Advanced

Maximum Students Taking Exam
Distribute Repeating Integers

Key takeaways

Dinic: BFS levels, then a blocking flow with a DFS that keeps a current-arc pointer; repeat until the sink is unreachable.
The sink distance rises every phase, so there are at most V phases; O(V²·E) overall.
On unit-capacity networks Dinic is much faster, which underlies Hopcroft-Karp for matching.