39.02Intermediate / Advanced4 topics16 min4 interactive animations

Max-flow/min-cut theorem

Every flow is at most the capacity of every cut, and when no augmenting path exists some cut has exactly the flow's value: maximum flow equals minimum cut, and the residual graph hands you both.

Learning goals

Compute the capacity of a cut and the flow across it
Explain why every flow value is at most every cut capacity
Use residual reachability as an optimality certificate
Extract a minimum cut from a maximum flow

Prerequisites

The flow network model

To find the narrowest bottleneck in a road network, draw a line separating the source from the sink and add up the capacities of the roads that cross it. The cheapest such line is a bottleneck no traffic can beat, and the theorem says it is exactly as wide as the best traffic pattern.

39.02.1

Cut capacity

An **s-t cut** is a set S of vertices that contains the source and not the sink. Its **capacity** is the sum of the capacities of the edges that go **from** S **to** the rest. Edges coming back into S do not count.

Load the cut question with “Cut capacity of S = {0, 1}” on the sample flow: the edges leaving {0, 1} are 0-2 (2), 1-2 (1) and 1-3 (2), so the capacity is 5. With “Cut capacity of S = {0}” the leaving edges are 0-1 (3) and 0-2 (2), also 5.

The key fact: for **any** valid flow, the flow value equals (flow out of S) minus (flow into S). Everything that leaves the source must cross the boundary of S somewhere, and conservation stops it piling up inside. The animation prints both numbers: on the sample flow 4 units leave and 0 return across both cuts.

Java

1static int cutCapacity(int[][] edges, boolean[] inS) {      // capacity of the edges leaving S (edges {from, to, capacity, flow})
2    int cap = 0;
3    for (int[] e : edges) if (inS[e[0]] && !inS[e[1]]) cap += e[2];
4    return cap;
5}
6
7static int flowAcrossCut(int[][] edges, boolean[] inS) {   // flow leaving S minus flow entering S
8    int net = 0;
9    for (int[] e : edges) {
10        if (inS[e[0]] && !inS[e[1]]) net += e[3];
11        if (!inS[e[0]] && inS[e[1]]) net -= e[3];
12    }
13    return net;
14}

A flow on a network: validity, residual graph, cuts and the optimality certificate

Interactive · edit the input

edge label: flow / capacity · 4 vertices · 5 edges

source

sink

Vertex or edge being checkedFineViolated rule or saturatedSource side S

Setup

A flow assigns each edge an amount between 0 and its capacity such that every vertex except the source 0 and the sink 3 receives as much as it sends. Label: flow / capacity.

Step 1 / 10

Java

1// edges[k] = {from, to, capacity, flow}; the source is 0 and the sink is n - 1
2static boolean isValidFlow(int n, int[][] edges) {
3    int[] balance = new int[n];                           // inflow minus outflow
4    for (int[] e : edges) {
5        if (e[3] < 0 || e[3] > e[2]) return false;        // capacity constraint: 0 <= flow <= capacity
6        balance[e[0]] -= e[3];
7        balance[e[1]] += e[3];
8    }
9    for (int v = 1; v < n - 1; v++) if (balance[v] != 0) return false;   // conservation at every inner vertex
10    return true;
11}
12static int flowValue(int n, int[][] edges) {              // net flow leaving the source
13    int value = 0;
14    for (int[] e : edges) { if (e[0] == 0) value += e[3]; if (e[1] == 0) value -= e[3]; }
15    return value;
16}
17static List<int[]> residualArcs(int[][] edges) {          // {from, to, remaining capacity}
18    List<int[]> arcs = new ArrayList<>();
19    for (int[] e : edges) {
20        if (e[2] - e[3] > 0) arcs.add(new int[]{e[0], e[1], e[2] - e[3]});   // forward: room left
21        if (e[3] > 0) arcs.add(new int[]{e[1], e[0], e[3]});                 // backward: flow that could be cancelled
22    }
23    return arcs;
24}
25static int cutCapacity(int[][] edges, boolean[] inS) {    // capacity of the edges leaving S
26    int cap = 0;
27    for (int[] e : edges) if (inS[e[0]] && !inS[e[1]]) cap += e[2];
28    return cap;
29}
30static boolean[] reachableInResidual(int n, int[][] edges) {   // vertices reachable from the source using residual arcs
31    boolean[] seen = new boolean[n];
32    seen[0] = true;
33    boolean changed = true;
34    while (changed) {
35        changed = false;
36        for (int[] a : residualArcs(edges)) if (seen[a[0]] && !seen[a[1]]) { seen[a[1]] = true; changed = true; }
37    }
38    return seen;
39}
40static boolean isMaximum(int n, int[][] edges) {          // valid flow, and the sink is cut off in the residual graph
41    return isValidFlow(n, edges) && !reachableInResidual(n, edges)[n - 1];
42}

Live state

0 checks0 residual arcs

edges

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2	n=4 edges=5	A flow assigns each edge an amount between 0 and its capacity such that every vertex except the source 0 and the sink 3 receives as much as it sends. Label: flow / capacity.
2	L5	edge=0→1 flow=2 capacity=3	Edge 0→1: 0 ≤ 2 ≤ 3. Capacity respected.
3	L5	edge=0→2 flow=2 capacity=2	Edge 0→2: 0 ≤ 2 ≤ 2. Capacity respected.
4	L5	edge=1→2 flow=0 capacity=1	Edge 1→2: 0 ≤ 0 ≤ 1. Capacity respected.
5	L5	edge=1→3 flow=2 capacity=2	Edge 1→3: 0 ≤ 2 ≤ 2. Capacity respected.
6	L5	edge=2→3 flow=2 capacity=3	Edge 2→3: 0 ≤ 2 ≤ 3. Capacity respected.
7	L9	vertex=1 inflow=2 outflow=2	Vertex 1: inflow 2 = outflow 2. Conservation holds.
8	L9	vertex=2 inflow=2 outflow=2	Vertex 2: inflow 2 = outflow 2. Conservation holds.
9	L12	value=4	Valid. The flow value is the net amount leaving the source: 4. It equals the net amount entering the sink.
10	L17	return=4 residual_arcs=7	Residual graph: each edge with room left gives a forward arc (capacity − flow); each edge with flow gives a reverse arc (the flow that could be cancelled). 7 arcs in all; the arcs marked * are reverse arcs.

39.02.2

Residual reachability

After a flow has been computed, run a search from the source in the residual graph and let S be every vertex it reaches. Two outcomes are possible. Either the sink is in S: you found an augmenting path. Or the sink is not in S: no augmenting path exists.

In the second case look at the boundary of S. An original edge leaving S must be **saturated** (flow = capacity), otherwise its forward arc would have let the search cross. An original edge entering S must carry **zero** flow, otherwise its backward arc would let the search cross. So across this boundary all edges are as full as possible going out and empty coming in.

Load the third question with “Maximum: the residual graph cuts off the sink”: the search reaches only {0}, and the two edges leaving 0 are both saturated.

Java

1static boolean[] reachableInResidual(int n, int[][] edges) {   // vertices reachable from the source along residual arcs
2    boolean[] seen = new boolean[n];
3    seen[0] = true;
4    boolean changed = true;
5    while (changed) {
6        changed = false;
7        for (int[] a : residualArcs(edges)) if (seen[a[0]] && !seen[a[1]]) { seen[a[1]] = true; changed = true; }
8    }
9    return seen;
10}

A flow on a network: validity, residual graph, cuts and the optimality certificate

Interactive · edit the input

edge label: flow / capacity · 4 vertices · 5 edges

source

sink

Vertex or edge being checkedFineViolated rule or saturatedSource side S

Setup

A flow assigns each edge an amount between 0 and its capacity such that every vertex except the source 0 and the sink 3 receives as much as it sends. Label: flow / capacity.

Step 1 / 10

Java

1// edges[k] = {from, to, capacity, flow}; the source is 0 and the sink is n - 1
2static boolean isValidFlow(int n, int[][] edges) {
3    int[] balance = new int[n];                           // inflow minus outflow
4    for (int[] e : edges) {
5        if (e[3] < 0 || e[3] > e[2]) return false;        // capacity constraint: 0 <= flow <= capacity
6        balance[e[0]] -= e[3];
7        balance[e[1]] += e[3];
8    }
9    for (int v = 1; v < n - 1; v++) if (balance[v] != 0) return false;   // conservation at every inner vertex
10    return true;
11}
12static int flowValue(int n, int[][] edges) {              // net flow leaving the source
13    int value = 0;
14    for (int[] e : edges) { if (e[0] == 0) value += e[3]; if (e[1] == 0) value -= e[3]; }
15    return value;
16}
17static List<int[]> residualArcs(int[][] edges) {          // {from, to, remaining capacity}
18    List<int[]> arcs = new ArrayList<>();
19    for (int[] e : edges) {
20        if (e[2] - e[3] > 0) arcs.add(new int[]{e[0], e[1], e[2] - e[3]});   // forward: room left
21        if (e[3] > 0) arcs.add(new int[]{e[1], e[0], e[3]});                 // backward: flow that could be cancelled
22    }
23    return arcs;
24}
25static int cutCapacity(int[][] edges, boolean[] inS) {    // capacity of the edges leaving S
26    int cap = 0;
27    for (int[] e : edges) if (inS[e[0]] && !inS[e[1]]) cap += e[2];
28    return cap;
29}
30static boolean[] reachableInResidual(int n, int[][] edges) {   // vertices reachable from the source using residual arcs
31    boolean[] seen = new boolean[n];
32    seen[0] = true;
33    boolean changed = true;
34    while (changed) {
35        changed = false;
36        for (int[] a : residualArcs(edges)) if (seen[a[0]] && !seen[a[1]]) { seen[a[1]] = true; changed = true; }
37    }
38    return seen;
39}
40static boolean isMaximum(int n, int[][] edges) {          // valid flow, and the sink is cut off in the residual graph
41    return isValidFlow(n, edges) && !reachableInResidual(n, edges)[n - 1];
42}

Live state

0 checks0 residual arcs

edges

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2	n=4 edges=5	A flow assigns each edge an amount between 0 and its capacity such that every vertex except the source 0 and the sink 3 receives as much as it sends. Label: flow / capacity.
2	L5	edge=0→1 flow=2 capacity=3	Edge 0→1: 0 ≤ 2 ≤ 3. Capacity respected.
3	L5	edge=0→2 flow=2 capacity=2	Edge 0→2: 0 ≤ 2 ≤ 2. Capacity respected.
4	L5	edge=1→2 flow=0 capacity=1	Edge 1→2: 0 ≤ 0 ≤ 1. Capacity respected.
5	L5	edge=1→3 flow=2 capacity=2	Edge 1→3: 0 ≤ 2 ≤ 2. Capacity respected.
6	L5	edge=2→3 flow=2 capacity=3	Edge 2→3: 0 ≤ 2 ≤ 3. Capacity respected.
7	L9	vertex=1 inflow=2 outflow=2	Vertex 1: inflow 2 = outflow 2. Conservation holds.
8	L9	vertex=2 inflow=2 outflow=2	Vertex 2: inflow 2 = outflow 2. Conservation holds.
9	L12	value=4	Valid. The flow value is the net amount leaving the source: 4. It equals the net amount entering the sink.
10	L17	return=4 residual_arcs=7	Residual graph: each edge with room left gives a forward arc (capacity − flow); each edge with flow gives a reverse arc (the flow that could be cancelled). 7 arcs in all; the arcs marked * are reverse arcs.

39.02.3

Optimality certificate

Because flow across the cut equals the flow value, and the flow out of S cannot exceed the capacity of the edges leaving S, **every flow value is at most every cut capacity**. Therefore if you exhibit one flow and one cut with equal numbers, the flow is maximum and the cut is minimum: the pair is a **certificate** anyone can check without trusting your algorithm.

The residual search builds that certificate automatically. When the sink is unreachable, the reachable set S is a cut whose capacity equals the flow value (all its leaving edges are saturated and all its entering edges are empty). On “Maximum: the residual graph cuts off the sink” the flow value is 5 and the cut {0} has capacity 5.

Checking is cheap: verify the two flow rules, run one residual search, and confirm the sink is unreachable.

Java

1static boolean isMaximum(int n, int[][] edges) {            // valid flow whose residual graph cuts the sink off
2    return respectsCapacity(edges) && conservationHolds(n, edges) && !reachableInResidual(n, edges)[n - 1];
3}

A flow on a network: validity, residual graph, cuts and the optimality certificate

Interactive · edit the input

edge label: flow / capacity · 4 vertices · 5 edges

source

sink

Vertex or edge being checkedFineViolated rule or saturatedSource side S

Setup

A flow assigns each edge an amount between 0 and its capacity such that every vertex except the source 0 and the sink 3 receives as much as it sends. Label: flow / capacity.

Step 1 / 10

Java

1// edges[k] = {from, to, capacity, flow}; the source is 0 and the sink is n - 1
2static boolean isValidFlow(int n, int[][] edges) {
3    int[] balance = new int[n];                           // inflow minus outflow
4    for (int[] e : edges) {
5        if (e[3] < 0 || e[3] > e[2]) return false;        // capacity constraint: 0 <= flow <= capacity
6        balance[e[0]] -= e[3];
7        balance[e[1]] += e[3];
8    }
9    for (int v = 1; v < n - 1; v++) if (balance[v] != 0) return false;   // conservation at every inner vertex
10    return true;
11}
12static int flowValue(int n, int[][] edges) {              // net flow leaving the source
13    int value = 0;
14    for (int[] e : edges) { if (e[0] == 0) value += e[3]; if (e[1] == 0) value -= e[3]; }
15    return value;
16}
17static List<int[]> residualArcs(int[][] edges) {          // {from, to, remaining capacity}
18    List<int[]> arcs = new ArrayList<>();
19    for (int[] e : edges) {
20        if (e[2] - e[3] > 0) arcs.add(new int[]{e[0], e[1], e[2] - e[3]});   // forward: room left
21        if (e[3] > 0) arcs.add(new int[]{e[1], e[0], e[3]});                 // backward: flow that could be cancelled
22    }
23    return arcs;
24}
25static int cutCapacity(int[][] edges, boolean[] inS) {    // capacity of the edges leaving S
26    int cap = 0;
27    for (int[] e : edges) if (inS[e[0]] && !inS[e[1]]) cap += e[2];
28    return cap;
29}
30static boolean[] reachableInResidual(int n, int[][] edges) {   // vertices reachable from the source using residual arcs
31    boolean[] seen = new boolean[n];
32    seen[0] = true;
33    boolean changed = true;
34    while (changed) {
35        changed = false;
36        for (int[] a : residualArcs(edges)) if (seen[a[0]] && !seen[a[1]]) { seen[a[1]] = true; changed = true; }
37    }
38    return seen;
39}
40static boolean isMaximum(int n, int[][] edges) {          // valid flow, and the sink is cut off in the residual graph
41    return isValidFlow(n, edges) && !reachableInResidual(n, edges)[n - 1];
42}

Live state

0 checks0 residual arcs

edges

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2	n=4 edges=5	A flow assigns each edge an amount between 0 and its capacity such that every vertex except the source 0 and the sink 3 receives as much as it sends. Label: flow / capacity.
2	L5	edge=0→1 flow=2 capacity=3	Edge 0→1: 0 ≤ 2 ≤ 3. Capacity respected.
3	L5	edge=0→2 flow=2 capacity=2	Edge 0→2: 0 ≤ 2 ≤ 2. Capacity respected.
4	L5	edge=1→2 flow=0 capacity=1	Edge 1→2: 0 ≤ 0 ≤ 1. Capacity respected.
5	L5	edge=1→3 flow=2 capacity=2	Edge 1→3: 0 ≤ 2 ≤ 2. Capacity respected.
6	L5	edge=2→3 flow=2 capacity=3	Edge 2→3: 0 ≤ 2 ≤ 3. Capacity respected.
7	L9	vertex=1 inflow=2 outflow=2	Vertex 1: inflow 2 = outflow 2. Conservation holds.
8	L9	vertex=2 inflow=2 outflow=2	Vertex 2: inflow 2 = outflow 2. Conservation holds.
9	L12	value=4	Valid. The flow value is the net amount leaving the source: 4. It equals the net amount entering the sink.
10	L17	return=4 residual_arcs=7	Residual graph: each edge with room left gives a forward arc (capacity − flow); each edge with flow gives a reverse arc (the flow that could be cancelled). 7 arcs in all; the arcs marked * are reverse arcs.

39.02.4

Flow-cut equality

**Max-flow min-cut theorem**: the value of a maximum flow equals the capacity of a minimum cut. The easy half (flow <= cut) is the argument above; the hard half is that equality is always reached, and it comes from the residual search: when an algorithm stops because no augmenting path remains, the reachable set is a cut of exactly the flow's value.

Try it: run the “Ford-Fulkerson on a small network” preset. The maximum flow is 19 and the final message names the minimum cut, the vertices {0, 2}; the edges leaving that set are 0→1 (capacity 10) and 2→4 (capacity 9), together 19. Every algorithm in the next lessons ends with this same message, because every one of them stops exactly when the residual graph has no augmenting path (push-relabel stops at an equivalent point).

This duality is the reason flow algorithms solve so many problems: finding the cheapest way to disconnect two vertices is the same problem as finding the largest amount that can be routed between them.

Java

1static List<int[]> minCutEdges(int n, int[][] edges) {      // for a maximum flow: the saturated edges leaving the reachable set
2    boolean[] inS = reachableInResidual(n, edges);
3    List<int[]> cut = new ArrayList<>();
4    for (int[] e : edges) if (inS[e[0]] && !inS[e[1]]) cut.add(e);
5    return cut;
6}

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.

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph

Medium

Minimum Number of Days to Disconnect Island
Number of Operations to Make Network Connected

Advanced

Minimum Cost to Make at Least One Valid Path in a Grid
Reachable Nodes In Subdivided Graph

Key takeaways

Cut capacity counts only edges leaving S.
Every flow value <= every cut capacity; equal values certify both are optimal.
When no augmenting path remains, the vertices reachable from the source form a minimum cut.