39.01Intermediate / Advanced6 topics18 min6 interactive animations

Flow network model

A flow network is a directed graph with capacities, a source and a sink. A flow respects the capacities and conserves material at every other vertex; the residual graph shows how a flow can still be improved.

Learning goals

State the capacity and conservation rules and check them for a given flow
Build the residual graph with forward and reverse arcs
Recognise an augmenting path and explain what pushing along it does
Explain why reverse arcs let a later path undo an earlier choice

Prerequisites

Directed graphs and shortest paths (Chapters 34-35)BFS and DFS

Think of pipes carrying water from a reservoir to a town. Each pipe has a maximum rate, nothing is created or lost at the junctions, and the question is how much water can reach the town. Traffic, data packets and supply chains obey the same two rules.

39.01.1

Source/sink

A **flow network** is a directed graph with a designated **source** s (where material enters) and **sink** t (where it leaves). In this chapter the source is vertex 0 and the sink is vertex n - 1. Every edge also has a capacity, covered next.

A **flow** puts a non-negative amount of material on each edge. Its **value** is the net amount leaving the source: flow on edges out of s minus flow on edges into s. By conservation (below) it equals the net amount arriving at the sink, so you can measure it at either end.

The goal of the whole chapter is the **maximum flow**: the largest value any valid flow can have. Open the animation and load “A valid flow of value 4”: the log checks every rule and then reports the value, 4.

Java

1// edges[k] = {from, to, capacity, flow}; the source is 0 and the sink is n - 1
2static int flowValue(int[][] edges) {                      // net flow leaving the source
3    int value = 0;
4    for (int[] e : edges) { if (e[0] == 0) value += e[3]; if (e[1] == 0) value -= e[3]; }
5    return value;
6}
7
8static int flowIntoSink(int n, int[][] edges) {            // net flow arriving at the sink: equals flowValue for a valid flow
9    int value = 0;
10    for (int[] e : edges) { if (e[1] == n - 1) value += e[3]; if (e[0] == n - 1) value -= e[3]; }
11    return value;
12}

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

Capacity

Each edge u → v has a **capacity** c, the most it can carry. A flow f must satisfy 0 <= f(u, v) <= c(u, v) for every edge. Capacities are whole numbers in this course's examples, but real networks (bandwidth, pipe diameters) use any non-negative number.

Load “Capacity exceeded on 1-3”: edge 1-3 has capacity 2 but is given 3 units. The animation flags that edge and reports the flow as invalid even though every vertex is balanced, because a flow has to satisfy both rules.

Parallel edges are allowed and are simply separate pipes between the same two vertices; their capacities add up.

Java

1static boolean respectsCapacity(int[][] edges) {
2    for (int[] e : edges) if (e[3] < 0 || e[3] > e[2]) return false;   // 0 <= flow <= capacity on every edge
3    return true;
4}

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

Conservation

**Conservation** says that every vertex other than the source and the sink passes on exactly what it receives: inflow equals outflow. Nothing is stored, created or destroyed in the middle of the network.

Load “Conservation broken at vertex 1”: vertex 1 receives 3 units on 0-1 but sends only 1 unit on 1-3. Two units vanish, so this is not a flow. The check is easy to implement as a balance array: subtract the flow from the tail and add it to the head of every edge, then every inner vertex must end at 0.

Conservation is also why the flow value can be measured at either end: the amount that leaves the source must arrive at the sink, because it cannot accumulate anywhere else.

Java

1static boolean conservationHolds(int n, int[][] edges) {
2    int[] balance = new int[n];                            // inflow minus outflow
3    for (int[] e : edges) { balance[e[0]] -= e[3]; balance[e[1]] += e[3]; }
4    for (int v = 1; v < n - 1; v++) if (balance[v] != 0) return false;
5    return true;
6}

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

Residual graph

The **residual graph** describes what can still change. For every edge u → v with capacity c and flow f it has up to two arcs: a **forward arc** u → v with residual capacity c - f (room left), and a **backward arc** v → u with residual capacity f (flow that could be cancelled). Arcs with residual capacity 0 are left out.

Load the “A valid flow of value 4” preset and run the first question. The graph has 5 edges and 7 residual arcs: 0-1 (2 of 3) gives a forward arc of 1 and a backward arc of 2; 0-2 (2 of 2) is full so only its backward arc remains; 1-2 (0 of 1) has only a forward arc; 1-3 (2 of 2) only a backward arc; 2-3 (2 of 3) both. In the animation the arcs marked with * are the backward ones.

The residual graph is the working data structure of every algorithm in this chapter. A path in it from the source to the sink is an augmenting path.

Java

1static List<int[]> residualArcs(int[][] edges) {           // {from, to, remaining capacity}
2    List<int[]> arcs = new ArrayList<>();
3    for (int[] e : edges) {
4        if (e[2] - e[3] > 0) arcs.add(new int[]{e[0], e[1], e[2] - e[3]});   // forward: room left
5        if (e[3] > 0) arcs.add(new int[]{e[1], e[0], e[3]});                 // backward: flow that could be cancelled
6    }
7    return arcs;
8}

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

Augmenting paths

An **augmenting path** is a path from the source to the sink in the residual graph. Its **bottleneck** is the smallest residual capacity on it. Pushing the bottleneck along the path raises the flow value by that amount: forward arcs gain flow, backward arcs lose flow.

If the residual graph has no such path the flow cannot be improved by this method, and (as the next lesson proves) it is already maximum. Load “Not maximum: an augmenting path remains” with the third question: the residual search reaches the sink along 0→1→2→3, so the flow of value 4 can still grow. Load “Maximum: the residual graph cuts off the sink” and the search stops at the source.

The code finds some augmenting path with BFS over the residual arcs. Algorithms differ only in how they choose the path.

Java

1static List<Integer> augmentingPath(int n, int[][] edges) {   // vertices of an s-t path in the residual graph, or empty
2    List<int[]> arcs = residualArcs(edges);
3    int[] parent = new int[n];
4    Arrays.fill(parent, -1);
5    parent[0] = 0;
6    Deque<Integer> queue = new ArrayDeque<>(List.of(0));
7    while (!queue.isEmpty() && parent[n - 1] == -1) {
8        int u = queue.poll();
9        for (int[] a : arcs) if (a[0] == u && parent[a[1]] == -1) { parent[a[1]] = u; queue.add(a[1]); }
10    }
11    LinkedList<Integer> path = new LinkedList<>();
12    if (parent[n - 1] == -1) return path;
13    for (int v = n - 1; v != 0; v = parent[v]) path.addFirst(v);
14    path.addFirst(0);
15    return path;
16}

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

Reverse edges

Why do backward arcs exist? Because a greedy choice may turn out wrong. On the “Reverse edges are needed” preset (0-1:1 0-2:1 1-2:1 1-3:1 2-3:1) the first path found is 0→1→2→3. That saturates 0-1, 1-2 and 2-3. Edge 0-2 is still free but leads to vertex 2, whose only way out (2-3) is full; edge 1-3 is free but can only be reached through vertex 1, whose entry (0-1) is full. A search that cannot undo anything is stuck at flow 1, yet the maximum flow is 2. The second path is 0→2→1→3, and its middle step 2→1 is a **backward arc**: it cancels the unit that 1-2 carried.

Cancelling is not an accident. A flow of value 2 here sends one unit along 0→1→3 and one along 0→2→3; the backward arc lets the algorithm rearrange the first path into that without ever starting over. Without backward arcs, augmenting-path algorithms can get stuck at a flow that is not maximum.

In code, store every edge as a **pair of arcs** with ids k and k ^ 1: the forward arc with the capacity and the backward arc with capacity 0. Pushing d units along arc k does cap[k] -= d and cap[k ^ 1] += d, which handles forward and backward moves in one line. The flow on the original edge is simply cap[k ^ 1].

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
7    @SuppressWarnings("unchecked")
8    Net(int n, int maxEdges) {
9        this.n = n; adj = new List[n]; to = new int[2 * maxEdges]; cap = new int[2 * maxEdges];
10        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
11    }
12
13    int addEdge(int u, int v, int c) {                  // returns the id of the forward arc; its flow is cap[id ^ 1]
14        int id = arcs;
15        to[arcs] = v; cap[arcs] = c; adj[u].add(arcs++);   // forward arc with the capacity
16        to[arcs] = u; cap[arcs] = 0; adj[v].add(arcs++);   // reverse arc: capacity 0 until flow is pushed
17        return id;
18    }
19
20    void push(int id, int d) { cap[id] -= d; cap[id ^ 1] += d; }   // use d units: shrink the arc, grow its reverse
21}

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

Medium

Number of Provinces
Cheapest Flights Within K Stops

Advanced

Remove Max Number of Edges to Keep Graph Fully Traversable
Minimum Cost to Make at Least One Valid Path in a Grid

Key takeaways

A flow obeys two rules: 0 <= flow <= capacity on each edge, and inflow = outflow at every inner vertex.
The residual graph has a forward arc (capacity - flow) and a backward arc (flow) per edge.
An augmenting path is a source-sink path in the residual graph; backward arcs let later paths undo earlier choices.