39.03Intermediate / Advanced4 topics15 min4 interactive animations

Ford-Fulkerson

Ford-Fulkerson repeats one idea: find any augmenting path in the residual graph and push its bottleneck. It always works for integer capacities, but the number of rounds depends on the path choices.

Learning goals

Run the augmenting-path method with DFS
Explain why integer capacities give an integer maximum flow
Compare path-selection rules
Build the example where a bad choice needs many rounds

Prerequisites

Residual graphsMax-flow min-cut

Imagine filling several connected tanks by hand: pour along any route that still has room, and keep going until no route is left. Ford-Fulkerson is exactly that, with the ability to also pour back.

39.03.1

Augmenting-path method

Start with zero flow. Repeat: search the residual graph for a path from s to t; if there is none, stop; otherwise push its bottleneck. When it stops the flow is maximum by the previous lesson.

The DFS version below is the shortest form of the method. dfs walks forward along arcs with positive residual capacity and returns the bottleneck of the first path it finds, updating arcs on the way back. Load the “Ford-Fulkerson on a small network” preset: it finds 5 augmenting paths and ends with flow 19.

Notice that the method is a recipe, not a single algorithm: its running time depends entirely on which path the search happens to find.

Java

1static int fordFulkerson(Net g, int s, int t) {
2    int flow = 0;
3    while (true) {
4        int pushed = dfs(g, s, t, Integer.MAX_VALUE, new boolean[g.n]);   // any augmenting path, found depth-first
5        if (pushed == 0) return flow;
6        flow += pushed;
7    }
8}
9
10static int dfs(Net g, int u, int t, int f, boolean[] seen) {
11    if (u == t) return f;
12    seen[u] = true;
13    for (int id : g.adj[u]) {
14        int v = g.to[id];
15        if (seen[v] || g.cap[id] == 0) continue;
16        int d = dfs(g, v, t, Math.min(f, g.cap[id]), seen);
17        if (d > 0) { g.cap[id] -= d; g.cap[id ^ 1] += d; return d; }      // use d units, open d units of reverse capacity
18    }
19    return 0;
20}

Worst

O(E · |f|) for integer capacities, where |f| is the maximum flow value

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

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

Integral capacity guarantee

If every capacity is an integer, every bottleneck is an integer, so every flow value along the way is an integer, and each round raises the flow by at least 1. The flow is bounded by the total capacity out of the source, so the method terminates, and the final flow assigns an **integer** to every edge. This is the **integrality theorem**.

It matters far beyond flow: when a combinatorial problem (matching, assignment, disjoint paths) is modelled as a flow with integer capacities, the maximum flow can be read as a choice of whole items. Chapter 40 uses exactly that for bipartite matching.

With irrational capacities the guarantee fails: there are networks where Ford-Fulkerson with unlucky path choices never terminates and converges to a value below the maximum. Algorithms with a bound that does not depend on capacities (next lessons) avoid this.

Java

1static int[] edgeFlows(Net g, int edgeCount) {               // edges were added in order, so edge k has forward arc 2k
2    int[] flow = new int[edgeCount];
3    for (int k = 0; k < edgeCount; k++) flow[k] = g.cap[2 * k + 1];   // the reverse arc holds exactly the flow
4    return flow;
5}

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

Path selection

The augmenting-path method says nothing about which path to take. Common rules and their worst-case behaviour:

Compare two choices on the same network. The “DFS takes the middle edge first” preset (0-1:9 0-2:9 1-2:1 1-3:9 2-3:9) makes the depth-first search use the tiny middle edge 1-2. It takes 4 augmentations, pushing 1, 8, 1 and 8 units, instead of the 2 augmentations of 9 units each that the “Edmonds-Karp avoids the middle edge” preset needs. The final flow is 18 either way; only the work differs.

Rule	Rounds in the worst case	Notes
Any path (DFS)	up to the flow value for integer capacities	Simple, but capacity-dependent
Fewest arcs (BFS): Edmonds-Karp	O(V · E)	Independent of capacities
Largest bottleneck first	O(E · log of the flow value)	Needs a priority queue
Capacity scaling	O(E · log C) rounds	Only paths with bottleneck at least a threshold that halves
Level graph and blocking flow: Dinic	O(V) phases	Next lesson

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

Complexity caveats

Each round costs O(E) and raises the flow by at least 1, so integer capacities give O(E · |f|). That is pseudo-polynomial: it grows with the **values** of the capacities, not just the size of the network.

The classic bad network has four vertices: 0-1 and 0-2 of capacity C, 1-3 and 2-3 of capacity C, and a middle edge 1-2 of capacity 1. If the search alternates between the paths 0→1→2→3 and 0→2→1→3 (the second crossing the middle edge backwards), each round pushes just 1 unit, so reaching the maximum flow 2C needs 2C augmentations. With C = 1000 that is 2000 rounds for a four-vertex graph, while two BFS-chosen paths of C units each would do.

The method below simulates the unlucky alternation and returns {augmentations, flow}; the result is {2C, 2C}. The lesson: never rely on the plain DFS version when capacities can be large, and prefer Edmonds-Karp or Dinic.

Java

1static int[] adversarialAugmentations(int C) {               // {augmentations, flow} when paths alternate through the middle edge
2    int[][] cap = {{0, C, C, 0}, {0, 0, 1, C}, {0, 0, 0, C}, {0, 0, 0, 0}};
3    int[][] paths = {{0, 1, 2, 3}, {0, 2, 1, 3}};            // the unlucky choices: forward through 1-2, then backward through it
4    int augmentations = 0, flow = 0;
5    for (int round = 0; round < 2 * C; round++) {
6        int[] p = paths[round % 2];
7        int b = Integer.MAX_VALUE;
8        for (int i = 0; i + 1 < p.length; i++) b = Math.min(b, cap[p[i]][p[i + 1]]);
9        for (int i = 0; i + 1 < p.length; i++) { cap[p[i]][p[i + 1]] -= b; cap[p[i + 1]][p[i]] += b; }
10        flow += b;
11        augmentations++;
12    }
13    return new int[]{augmentations, flow};
14}

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 the Town Judge

Medium

Number of Provinces
Network Delay Time

Advanced

Maximum Students Taking Exam
Distribute Repeating Integers

Key takeaways

Ford-Fulkerson: repeat any augmenting path until none exists; the result is a maximum flow.
Integer capacities give an integer flow, and O(E · |f|) rounds at most.
A bad path choice can need as many rounds as the flow value; choose paths with a rule that bounds them.