39.07Intermediate / Advanced4 topics17 min4 interactive animations

Min-cost flow

Min-cost flow asks for the cheapest way to send a given amount of flow. Successive shortest paths augments along the cheapest residual path each time; reverse arcs carry negative costs, which potentials let Dijkstra handle.

Learning goals

Define min-cost flow and read costed edges
Explain why reverse arcs have negative cost
Run successive shortest paths with Bellman-Ford
Use potentials so Dijkstra can replace Bellman-Ford

Prerequisites

Maximum flowShortest paths with negative edges (Chapter 35)

A delivery company has several routes with different capacities and prices per parcel. Sending the most parcels is not enough; it wants the cheapest plan that still ships everything.

39.07.1

Costed edges

In a **min-cost flow** problem each edge has a capacity c and a cost w per unit of flow. The cost of a flow is the sum over edges of flow × w. Given a required amount of flow (or “as much as possible”) from s to t, find the flow of that value with the smallest total cost.

Open the animation: each edge shows flow / capacity · cost. The default network 0-1:3/1 0-2:2/2 1-2:1/1 1-3:2/3 2-3:3/1 lets 5 units through; the cheapest plan costs 17.

The representation extends the flow network by a cost per arc. The reverse arc of an edge with cost w gets cost −w, because pushing flow back along it undoes some flow and so refunds its cost.

Java

1static class CostNet {
2    final int n;
3    final List<Integer>[] adj;                          // adj[u]: ids of the arcs leaving u
4    final int[] to, cap, cost;                          // arc k and arc k ^ 1 are each other's reverse
5    int arcs = 0;
6
7    @SuppressWarnings("unchecked")
8    CostNet(int n, int maxEdges) {
9        this.n = n; adj = new List[n]; to = new int[2 * maxEdges]; cap = new int[2 * maxEdges]; cost = new int[2 * maxEdges];
10        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
11    }
12
13    void addEdge(int u, int v, int c, int w) {
14        to[arcs] = v; cap[arcs] = c; cost[arcs] = w; adj[u].add(arcs++);
15        to[arcs] = u; cap[arcs] = 0; cost[arcs] = -w; adj[v].add(arcs++);   // undoing flow gives the cost back
16    }
17}

Min-cost flow: successive shortest augmenting paths, potentials

Interactive · edit the input

edge label: flow / capacity · cost per unit · 4 vertices · 5 edges

source

sink

Cheapest path being usedEdge carrying flowSaturated edge

residual arcs u→v : capacity @ cost

0→1:3@1

0→2:2@2

1→2:1@1

1→3:2@3

2→3:3@1

Setup

Send as much flow as possible from 0 to 3 at the lowest total cost. Each edge shows flow / capacity and its cost per unit. Repeatedly take the cheapest residual path from 0 to 3; pushing along reverse arcs undoes flow and gives its cost back, which is why reverse arcs have negative cost.

Step 1 / 9

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, cost;                         // 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]; cost = 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, int w) {
12        to[arcs] = v; cap[arcs] = c; cost[arcs] = w; adj[u].add(arcs++);
13        to[arcs] = u; cap[arcs] = 0; cost[arcs] = -w; adj[v].add(arcs++);   // undoing flow gives the cost back
14    }
15}
16static long[] minCostFlowBellmanFord(Net g, int s, int t, int want) {   // {flow, cost}; want 0 = as much flow as possible
17    long flow = 0, total = 0, inf = Long.MAX_VALUE / 2;
18    while (want == 0 || flow < want) {
19        long[] dist = new long[g.n];
20        Arrays.fill(dist, inf);
21        dist[s] = 0;
22        int[] via = new int[g.n];
23        Arrays.fill(via, -1);
24        for (int round = 0; round < g.n - 1; round++) {                 // Bellman-Ford copes with negative reverse-arc costs
25            boolean changed = false;
26            for (int u = 0; u < g.n; u++) {
27                if (dist[u] == inf) continue;
28                for (int id : g.adj[u]) {
29                    int v = g.to[id];
30                    if (g.cap[id] > 0 && dist[u] + g.cost[id] < dist[v]) { dist[v] = dist[u] + g.cost[id]; via[v] = id; changed = true; }
31                }
32            }
33            if (!changed) break;
34        }
35        if (dist[t] == inf) break;                                      // no augmenting path is left
36        long push = want == 0 ? Integer.MAX_VALUE : want - flow;
37        for (int v = t; v != s; v = g.to[via[v] ^ 1]) push = Math.min(push, g.cap[via[v]]);
38        for (int v = t; v != s; v = g.to[via[v] ^ 1]) { g.cap[via[v]] -= push; g.cap[via[v] ^ 1] += push; }
39        flow += push;
40        total += push * dist[t];                                        // every unit of this path costs dist[t]
41    }
42    return new long[]{flow, total};
43}
44static long[] minCostFlowPotentials(Net g, int s, int t, int want) {    // needs every original cost >= 0
45    long flow = 0, total = 0, inf = Long.MAX_VALUE / 2;
46    long[] h = new long[g.n];                                           // potentials: reduced cost = cost + h[u] - h[v] >= 0
47    while (want == 0 || flow < want) {
48        long[] dist = new long[g.n];
49        Arrays.fill(dist, inf);
50        dist[s] = 0;
51        int[] via = new int[g.n];
52        Arrays.fill(via, -1);
53        PriorityQueue<long[]> pq = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));
54        pq.add(new long[]{0, s});
55        while (!pq.isEmpty()) {                                         // Dijkstra on reduced costs
56            long[] top = pq.poll();
57            int u = (int) top[1];
58            if (top[0] > dist[u]) continue;
59            for (int id : g.adj[u]) {
60                int v = g.to[id];
61                long nd = dist[u] + g.cost[id] + h[u] - h[v];
62                if (g.cap[id] > 0 && nd < dist[v]) { dist[v] = nd; via[v] = id; pq.add(new long[]{nd, v}); }
63            }
64        }
65        if (dist[t] == inf) break;
66        for (int v = 0; v < g.n; v++) if (dist[v] < inf) h[v] += dist[v];  // keep reduced costs non-negative next round
67        long push = want == 0 ? Integer.MAX_VALUE : want - flow;
68        for (int v = t; v != s; v = g.to[via[v] ^ 1]) push = Math.min(push, g.cap[via[v]]);
69        for (int v = t; v != s; v = g.to[via[v] ^ 1]) { g.cap[via[v]] -= push; g.cap[via[v] ^ 1] += push; }
70        flow += push;
71        total += push * (h[t] - h[s]);                                  // h[t] - h[s] is the true cost of the path
72    }
73    return new long[]{flow, total};
74}

Live state

0 augmentations0 relaxations

edges

wanted

max

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L16	n=4 edges=5 wanted=max	Send as much flow as possible from 0 to 3 at the lowest total cost. Each edge shows flow / capacity and its cost per unit. Repeatedly take the cheapest residual path from 0 to 3; pushing along reverse arcs undoes flow and gives its cost back, which is why reverse arcs have negative cost.
2	L36	path=0→2→3 path_cost=3 push=2	Cheapest residual path: 0→2→3, cost 3 per unit. Bottleneck 2.
3	L40	flow=2 cost=6	Push 2 units: 2 × 3 = 6. Total flow 2, total cost 6.
4	L36	path=0→1→2→3 path_cost=3 push=1	Cheapest residual path: 0→1→2→3, cost 3 per unit. Bottleneck 1.
5	L40	flow=3 cost=9	Push 1 unit: 1 × 3 = 3. Total flow 3, total cost 9.
6	L36	path=0→1→3 path_cost=4 push=2	Cheapest residual path: 0→1→3, cost 4 per unit. Bottleneck 2.
7	L40	flow=5 cost=17	Push 2 units: 2 × 4 = 8. Total flow 5, total cost 17.
8	L35	flow=5 cost=17	No residual path from 0 to 3 exists: the network cannot carry more flow.
9	L42	return=17 flow=5 augmentations=3	Minimum cost of 5 units of flow: 17, found with 3 augmentations. Every augmentation used a cheapest path, and the path costs never decrease from one round to the next.

39.07.2

Residual negative costs

Negative arc costs appear even if all original costs are non-negative. On the “A negative reverse arc is used” preset (0-1:1/1 0-2:1/5 1-2:1/1 1-3:1/5 2-3:1/1) the first cheapest path is 0→1→2→3 with cost 3. For the second unit the cheapest residual path is 0→2→1→3, and its middle step 2→1 is a reverse arc of cost −1: it cancels the unit sent over 1→2 and reroutes it through 1→3. The path costs 5 − 1 + 5 = 9, and the total for 2 units is 12.

Because costs can be negative, shortest paths in the residual graph need Bellman-Ford (Chapter 35). There is never a negative cycle in the residual graph as long as the current flow is a minimum-cost flow for its value; this invariant is exactly what the algorithm maintains.

Bellman-Ford costs O(V·E) per augmentation. The method below is the complete algorithm with that choice.

Java

1static long[] minCostFlowBellmanFord(CostNet g, int s, int t, int want) {   // {flow, cost}; want 0 = as much flow as possible
2    long flow = 0, total = 0, inf = Long.MAX_VALUE / 2;
3    while (want == 0 || flow < want) {
4        long[] dist = new long[g.n];
5        Arrays.fill(dist, inf);
6        dist[s] = 0;
7        int[] via = new int[g.n];
8        Arrays.fill(via, -1);
9        for (int round = 0; round < g.n - 1; round++) {                 // Bellman-Ford copes with negative reverse-arc costs
10            boolean changed = false;
11            for (int u = 0; u < g.n; u++) {
12                if (dist[u] == inf) continue;
13                for (int id : g.adj[u]) {
14                    int v = g.to[id];
15                    if (g.cap[id] > 0 && dist[u] + g.cost[id] < dist[v]) { dist[v] = dist[u] + g.cost[id]; via[v] = id; changed = true; }
16                }
17            }
18            if (!changed) break;
19        }
20        if (dist[t] == inf) break;                                      // no augmenting path is left
21        long push = want == 0 ? Integer.MAX_VALUE : want - flow;
22        for (int v = t; v != s; v = g.to[via[v] ^ 1]) push = Math.min(push, g.cap[via[v]]);
23        for (int v = t; v != s; v = g.to[via[v] ^ 1]) { g.cap[via[v]] -= push; g.cap[via[v] ^ 1] += push; }
24        flow += push;
25        total += push * dist[t];                                        // every unit of this path costs dist[t]
26    }
27    return new long[]{flow, total};
28}

Min-cost flow: successive shortest augmenting paths, potentials

Interactive · edit the input

edge label: flow / capacity · cost per unit · 4 vertices · 5 edges

source

sink

Cheapest path being usedEdge carrying flowSaturated edge

residual arcs u→v : capacity @ cost

0→1:3@1

0→2:2@2

1→2:1@1

1→3:2@3

2→3:3@1

Setup

Step 1 / 9

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, cost;                         // 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]; cost = 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, int w) {
12        to[arcs] = v; cap[arcs] = c; cost[arcs] = w; adj[u].add(arcs++);
13        to[arcs] = u; cap[arcs] = 0; cost[arcs] = -w; adj[v].add(arcs++);   // undoing flow gives the cost back
14    }
15}
16static long[] minCostFlowBellmanFord(Net g, int s, int t, int want) {   // {flow, cost}; want 0 = as much flow as possible
17    long flow = 0, total = 0, inf = Long.MAX_VALUE / 2;
18    while (want == 0 || flow < want) {
19        long[] dist = new long[g.n];
20        Arrays.fill(dist, inf);
21        dist[s] = 0;
22        int[] via = new int[g.n];
23        Arrays.fill(via, -1);
24        for (int round = 0; round < g.n - 1; round++) {                 // Bellman-Ford copes with negative reverse-arc costs
25            boolean changed = false;
26            for (int u = 0; u < g.n; u++) {
27                if (dist[u] == inf) continue;
28                for (int id : g.adj[u]) {
29                    int v = g.to[id];
30                    if (g.cap[id] > 0 && dist[u] + g.cost[id] < dist[v]) { dist[v] = dist[u] + g.cost[id]; via[v] = id; changed = true; }
31                }
32            }
33            if (!changed) break;
34        }
35        if (dist[t] == inf) break;                                      // no augmenting path is left
36        long push = want == 0 ? Integer.MAX_VALUE : want - flow;
37        for (int v = t; v != s; v = g.to[via[v] ^ 1]) push = Math.min(push, g.cap[via[v]]);
38        for (int v = t; v != s; v = g.to[via[v] ^ 1]) { g.cap[via[v]] -= push; g.cap[via[v] ^ 1] += push; }
39        flow += push;
40        total += push * dist[t];                                        // every unit of this path costs dist[t]
41    }
42    return new long[]{flow, total};
43}
44static long[] minCostFlowPotentials(Net g, int s, int t, int want) {    // needs every original cost >= 0
45    long flow = 0, total = 0, inf = Long.MAX_VALUE / 2;
46    long[] h = new long[g.n];                                           // potentials: reduced cost = cost + h[u] - h[v] >= 0
47    while (want == 0 || flow < want) {
48        long[] dist = new long[g.n];
49        Arrays.fill(dist, inf);
50        dist[s] = 0;
51        int[] via = new int[g.n];
52        Arrays.fill(via, -1);
53        PriorityQueue<long[]> pq = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));
54        pq.add(new long[]{0, s});
55        while (!pq.isEmpty()) {                                         // Dijkstra on reduced costs
56            long[] top = pq.poll();
57            int u = (int) top[1];
58            if (top[0] > dist[u]) continue;
59            for (int id : g.adj[u]) {
60                int v = g.to[id];
61                long nd = dist[u] + g.cost[id] + h[u] - h[v];
62                if (g.cap[id] > 0 && nd < dist[v]) { dist[v] = nd; via[v] = id; pq.add(new long[]{nd, v}); }
63            }
64        }
65        if (dist[t] == inf) break;
66        for (int v = 0; v < g.n; v++) if (dist[v] < inf) h[v] += dist[v];  // keep reduced costs non-negative next round
67        long push = want == 0 ? Integer.MAX_VALUE : want - flow;
68        for (int v = t; v != s; v = g.to[via[v] ^ 1]) push = Math.min(push, g.cap[via[v]]);
69        for (int v = t; v != s; v = g.to[via[v] ^ 1]) { g.cap[via[v]] -= push; g.cap[via[v] ^ 1] += push; }
70        flow += push;
71        total += push * (h[t] - h[s]);                                  // h[t] - h[s] is the true cost of the path
72    }
73    return new long[]{flow, total};
74}

Live state

0 augmentations0 relaxations

edges

wanted

max

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L16	n=4 edges=5 wanted=max	Send as much flow as possible from 0 to 3 at the lowest total cost. Each edge shows flow / capacity and its cost per unit. Repeatedly take the cheapest residual path from 0 to 3; pushing along reverse arcs undoes flow and gives its cost back, which is why reverse arcs have negative cost.
2	L36	path=0→2→3 path_cost=3 push=2	Cheapest residual path: 0→2→3, cost 3 per unit. Bottleneck 2.
3	L40	flow=2 cost=6	Push 2 units: 2 × 3 = 6. Total flow 2, total cost 6.
4	L36	path=0→1→2→3 path_cost=3 push=1	Cheapest residual path: 0→1→2→3, cost 3 per unit. Bottleneck 1.
5	L40	flow=3 cost=9	Push 1 unit: 1 × 3 = 3. Total flow 3, total cost 9.
6	L36	path=0→1→3 path_cost=4 push=2	Cheapest residual path: 0→1→3, cost 4 per unit. Bottleneck 2.
7	L40	flow=5 cost=17	Push 2 units: 2 × 4 = 8. Total flow 5, total cost 17.
8	L35	flow=5 cost=17	No residual path from 0 to 3 exists: the network cannot carry more flow.
9	L42	return=17 flow=5 augmentations=3	Minimum cost of 5 units of flow: 17, found with 3 augmentations. Every augmentation used a cheapest path, and the path costs never decrease from one round to the next.

39.07.3

Potentials

To use the faster Dijkstra we need non-negative arc costs. Keep a **potential** h[v] for every vertex (a previous shortest distance) and replace each arc cost by its **reduced cost** cost(u, v) + h[u] − h[v]. Any path from s to t changes by the same constant h[s] − h[t], so shortest paths stay shortest, and if the potentials are shortest distances then every residual arc has reduced cost ≥ 0.

After each Dijkstra run add the distances to the potentials: h[v] += dist[v] for reachable v. The reduced costs along the path just used become 0, and the new reverse arcs have reduced cost 0 as well, so the invariant is kept. The true cost of the path is h[t] − h[s]. The animation's second method (“potentials and Dijkstra”) throws an error if it ever meets a negative reduced cost, and the test suite never triggers it.

Initial potentials of 0 are valid because the original costs are non-negative. With negative original costs you would first run Bellman-Ford once to initialise them.

Java

1static long[] minCostFlowPotentials(CostNet g, int s, int t, int want) {    // needs every original cost >= 0
2    long flow = 0, total = 0, inf = Long.MAX_VALUE / 2;
3    long[] h = new long[g.n];                                           // potentials: reduced cost = cost + h[u] - h[v] >= 0
4    while (want == 0 || flow < want) {
5        long[] dist = new long[g.n];
6        Arrays.fill(dist, inf);
7        dist[s] = 0;
8        int[] via = new int[g.n];
9        Arrays.fill(via, -1);
10        PriorityQueue<long[]> pq = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));
11        pq.add(new long[]{0, s});
12        while (!pq.isEmpty()) {                                         // Dijkstra on reduced costs
13            long[] top = pq.poll();
14            int u = (int) top[1];
15            if (top[0] > dist[u]) continue;
16            for (int id : g.adj[u]) {
17                int v = g.to[id];
18                long nd = dist[u] + g.cost[id] + h[u] - h[v];
19                if (g.cap[id] > 0 && nd < dist[v]) { dist[v] = nd; via[v] = id; pq.add(new long[]{nd, v}); }
20            }
21        }
22        if (dist[t] == inf) break;
23        for (int v = 0; v < g.n; v++) if (dist[v] < inf) h[v] += dist[v];   // keep reduced costs non-negative next round
24        long push = want == 0 ? Integer.MAX_VALUE : want - flow;
25        for (int v = t; v != s; v = g.to[via[v] ^ 1]) push = Math.min(push, g.cap[via[v]]);
26        for (int v = t; v != s; v = g.to[via[v] ^ 1]) { g.cap[via[v]] -= push; g.cap[via[v] ^ 1] += push; }
27        flow += push;
28        total += push * (h[t] - h[s]);                                  // h[t] - h[s] is the true cost of the path
29    }
30    return new long[]{flow, total};
31}

Min-cost flow: successive shortest augmenting paths, potentials

Interactive · edit the input

edge label: flow / capacity · cost per unit · 4 vertices · 5 edges

source

sink

Cheapest path being usedEdge carrying flowSaturated edge

residual arcs u→v : capacity @ cost

0→1:3@1

0→2:2@2

1→2:1@1

1→3:2@3

2→3:3@1

Setup

Step 1 / 9

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, cost;                         // 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]; cost = 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, int w) {
12        to[arcs] = v; cap[arcs] = c; cost[arcs] = w; adj[u].add(arcs++);
13        to[arcs] = u; cap[arcs] = 0; cost[arcs] = -w; adj[v].add(arcs++);   // undoing flow gives the cost back
14    }
15}
16static long[] minCostFlowBellmanFord(Net g, int s, int t, int want) {   // {flow, cost}; want 0 = as much flow as possible
17    long flow = 0, total = 0, inf = Long.MAX_VALUE / 2;
18    while (want == 0 || flow < want) {
19        long[] dist = new long[g.n];
20        Arrays.fill(dist, inf);
21        dist[s] = 0;
22        int[] via = new int[g.n];
23        Arrays.fill(via, -1);
24        for (int round = 0; round < g.n - 1; round++) {                 // Bellman-Ford copes with negative reverse-arc costs
25            boolean changed = false;
26            for (int u = 0; u < g.n; u++) {
27                if (dist[u] == inf) continue;
28                for (int id : g.adj[u]) {
29                    int v = g.to[id];
30                    if (g.cap[id] > 0 && dist[u] + g.cost[id] < dist[v]) { dist[v] = dist[u] + g.cost[id]; via[v] = id; changed = true; }
31                }
32            }
33            if (!changed) break;
34        }
35        if (dist[t] == inf) break;                                      // no augmenting path is left
36        long push = want == 0 ? Integer.MAX_VALUE : want - flow;
37        for (int v = t; v != s; v = g.to[via[v] ^ 1]) push = Math.min(push, g.cap[via[v]]);
38        for (int v = t; v != s; v = g.to[via[v] ^ 1]) { g.cap[via[v]] -= push; g.cap[via[v] ^ 1] += push; }
39        flow += push;
40        total += push * dist[t];                                        // every unit of this path costs dist[t]
41    }
42    return new long[]{flow, total};
43}
44static long[] minCostFlowPotentials(Net g, int s, int t, int want) {    // needs every original cost >= 0
45    long flow = 0, total = 0, inf = Long.MAX_VALUE / 2;
46    long[] h = new long[g.n];                                           // potentials: reduced cost = cost + h[u] - h[v] >= 0
47    while (want == 0 || flow < want) {
48        long[] dist = new long[g.n];
49        Arrays.fill(dist, inf);
50        dist[s] = 0;
51        int[] via = new int[g.n];
52        Arrays.fill(via, -1);
53        PriorityQueue<long[]> pq = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));
54        pq.add(new long[]{0, s});
55        while (!pq.isEmpty()) {                                         // Dijkstra on reduced costs
56            long[] top = pq.poll();
57            int u = (int) top[1];
58            if (top[0] > dist[u]) continue;
59            for (int id : g.adj[u]) {
60                int v = g.to[id];
61                long nd = dist[u] + g.cost[id] + h[u] - h[v];
62                if (g.cap[id] > 0 && nd < dist[v]) { dist[v] = nd; via[v] = id; pq.add(new long[]{nd, v}); }
63            }
64        }
65        if (dist[t] == inf) break;
66        for (int v = 0; v < g.n; v++) if (dist[v] < inf) h[v] += dist[v];  // keep reduced costs non-negative next round
67        long push = want == 0 ? Integer.MAX_VALUE : want - flow;
68        for (int v = t; v != s; v = g.to[via[v] ^ 1]) push = Math.min(push, g.cap[via[v]]);
69        for (int v = t; v != s; v = g.to[via[v] ^ 1]) { g.cap[via[v]] -= push; g.cap[via[v] ^ 1] += push; }
70        flow += push;
71        total += push * (h[t] - h[s]);                                  // h[t] - h[s] is the true cost of the path
72    }
73    return new long[]{flow, total};
74}

Live state

0 augmentations0 relaxations

edges

wanted

max

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L16	n=4 edges=5 wanted=max	Send as much flow as possible from 0 to 3 at the lowest total cost. Each edge shows flow / capacity and its cost per unit. Repeatedly take the cheapest residual path from 0 to 3; pushing along reverse arcs undoes flow and gives its cost back, which is why reverse arcs have negative cost.
2	L36	path=0→2→3 path_cost=3 push=2	Cheapest residual path: 0→2→3, cost 3 per unit. Bottleneck 2.
3	L40	flow=2 cost=6	Push 2 units: 2 × 3 = 6. Total flow 2, total cost 6.
4	L36	path=0→1→2→3 path_cost=3 push=1	Cheapest residual path: 0→1→2→3, cost 3 per unit. Bottleneck 1.
5	L40	flow=3 cost=9	Push 1 unit: 1 × 3 = 3. Total flow 3, total cost 9.
6	L36	path=0→1→3 path_cost=4 push=2	Cheapest residual path: 0→1→3, cost 4 per unit. Bottleneck 2.
7	L40	flow=5 cost=17	Push 2 units: 2 × 4 = 8. Total flow 5, total cost 17.
8	L35	flow=5 cost=17	No residual path from 0 to 3 exists: the network cannot carry more flow.
9	L42	return=17 flow=5 augmentations=3	Minimum cost of 5 units of flow: 17, found with 3 augmentations. Every augmentation used a cheapest path, and the path costs never decrease from one round to the next.

39.07.4

Successive shortest augmenting path

**Successive shortest augmenting paths** is the whole algorithm: repeatedly find a cheapest path in the residual graph and push its bottleneck (or only as many units as still wanted). Path costs never decrease from one round to the next, and the flow after k units is a minimum-cost flow of value k.

On the default network the rounds cost 3, 3 and 4 per unit: two units over 0→2→3 (cost 3 each, 6), one unit over 0→1→2→3 (3), and two units over 0→1→3 (4 each, 8), a total of 17 for 5 units. Ask for only 3 units with the “Only 3 units wanted” preset and the cost is 9. Ask for more than the network allows (“More flow wanted than possible”): the algorithm stops with the maximum flow 2 and cost 6.

The method builds the network from edge records and returns the cost, or −1 if fewer than k units fit.

Java

1static long minCostForUnits(int n, int[][] edges, int s, int t, int k) {   // edges {from, to, capacity, cost}; -1 if k units do not fit
2    CostNet g = new CostNet(n, edges.length);
3    for (int[] e : edges) g.addEdge(e[0], e[1], e[2], e[3]);
4    long[] r = minCostFlowBellmanFord(g, s, t, k);
5    return r[0] < k ? -1 : r[1];
6}

Worst

O(F · V · E) with Bellman-Ford, O(F · E log V) with potentials and a heap (F = units of flow)

Space

O(V + E)

Min-cost flow: successive shortest augmenting paths, potentials

Interactive · edit the input

edge label: flow / capacity · cost per unit · 4 vertices · 5 edges

source

sink

Cheapest path being usedEdge carrying flowSaturated edge

residual arcs u→v : capacity @ cost

0→1:3@1

0→2:2@2

1→2:1@1

1→3:2@3

2→3:3@1

Setup

Step 1 / 9

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, cost;                         // 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]; cost = 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, int w) {
12        to[arcs] = v; cap[arcs] = c; cost[arcs] = w; adj[u].add(arcs++);
13        to[arcs] = u; cap[arcs] = 0; cost[arcs] = -w; adj[v].add(arcs++);   // undoing flow gives the cost back
14    }
15}
16static long[] minCostFlowBellmanFord(Net g, int s, int t, int want) {   // {flow, cost}; want 0 = as much flow as possible
17    long flow = 0, total = 0, inf = Long.MAX_VALUE / 2;
18    while (want == 0 || flow < want) {
19        long[] dist = new long[g.n];
20        Arrays.fill(dist, inf);
21        dist[s] = 0;
22        int[] via = new int[g.n];
23        Arrays.fill(via, -1);
24        for (int round = 0; round < g.n - 1; round++) {                 // Bellman-Ford copes with negative reverse-arc costs
25            boolean changed = false;
26            for (int u = 0; u < g.n; u++) {
27                if (dist[u] == inf) continue;
28                for (int id : g.adj[u]) {
29                    int v = g.to[id];
30                    if (g.cap[id] > 0 && dist[u] + g.cost[id] < dist[v]) { dist[v] = dist[u] + g.cost[id]; via[v] = id; changed = true; }
31                }
32            }
33            if (!changed) break;
34        }
35        if (dist[t] == inf) break;                                      // no augmenting path is left
36        long push = want == 0 ? Integer.MAX_VALUE : want - flow;
37        for (int v = t; v != s; v = g.to[via[v] ^ 1]) push = Math.min(push, g.cap[via[v]]);
38        for (int v = t; v != s; v = g.to[via[v] ^ 1]) { g.cap[via[v]] -= push; g.cap[via[v] ^ 1] += push; }
39        flow += push;
40        total += push * dist[t];                                        // every unit of this path costs dist[t]
41    }
42    return new long[]{flow, total};
43}
44static long[] minCostFlowPotentials(Net g, int s, int t, int want) {    // needs every original cost >= 0
45    long flow = 0, total = 0, inf = Long.MAX_VALUE / 2;
46    long[] h = new long[g.n];                                           // potentials: reduced cost = cost + h[u] - h[v] >= 0
47    while (want == 0 || flow < want) {
48        long[] dist = new long[g.n];
49        Arrays.fill(dist, inf);
50        dist[s] = 0;
51        int[] via = new int[g.n];
52        Arrays.fill(via, -1);
53        PriorityQueue<long[]> pq = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));
54        pq.add(new long[]{0, s});
55        while (!pq.isEmpty()) {                                         // Dijkstra on reduced costs
56            long[] top = pq.poll();
57            int u = (int) top[1];
58            if (top[0] > dist[u]) continue;
59            for (int id : g.adj[u]) {
60                int v = g.to[id];
61                long nd = dist[u] + g.cost[id] + h[u] - h[v];
62                if (g.cap[id] > 0 && nd < dist[v]) { dist[v] = nd; via[v] = id; pq.add(new long[]{nd, v}); }
63            }
64        }
65        if (dist[t] == inf) break;
66        for (int v = 0; v < g.n; v++) if (dist[v] < inf) h[v] += dist[v];  // keep reduced costs non-negative next round
67        long push = want == 0 ? Integer.MAX_VALUE : want - flow;
68        for (int v = t; v != s; v = g.to[via[v] ^ 1]) push = Math.min(push, g.cap[via[v]]);
69        for (int v = t; v != s; v = g.to[via[v] ^ 1]) { g.cap[via[v]] -= push; g.cap[via[v] ^ 1] += push; }
70        flow += push;
71        total += push * (h[t] - h[s]);                                  // h[t] - h[s] is the true cost of the path
72    }
73    return new long[]{flow, total};
74}

Live state

0 augmentations0 relaxations

edges

wanted

max

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L16	n=4 edges=5 wanted=max	Send as much flow as possible from 0 to 3 at the lowest total cost. Each edge shows flow / capacity and its cost per unit. Repeatedly take the cheapest residual path from 0 to 3; pushing along reverse arcs undoes flow and gives its cost back, which is why reverse arcs have negative cost.
2	L36	path=0→2→3 path_cost=3 push=2	Cheapest residual path: 0→2→3, cost 3 per unit. Bottleneck 2.
3	L40	flow=2 cost=6	Push 2 units: 2 × 3 = 6. Total flow 2, total cost 6.
4	L36	path=0→1→2→3 path_cost=3 push=1	Cheapest residual path: 0→1→2→3, cost 3 per unit. Bottleneck 1.
5	L40	flow=3 cost=9	Push 1 unit: 1 × 3 = 3. Total flow 3, total cost 9.
6	L36	path=0→1→3 path_cost=4 push=2	Cheapest residual path: 0→1→3, cost 4 per unit. Bottleneck 2.
7	L40	flow=5 cost=17	Push 2 units: 2 × 4 = 8. Total flow 5, total cost 17.
8	L35	flow=5 cost=17	No residual path from 0 to 3 exists: the network cannot carry more flow.
9	L42	return=17 flow=5 augmentations=3	Minimum cost of 5 units of flow: 17, found with 3 augmentations. Every augmentation used a cheapest path, and the path costs never decrease from one round to the next.

Practice ladder

Now try it yourself

Easy

Min Cost Climbing Stairs

Medium

Cheapest Flights Within K Stops
Network Delay Time

Advanced

Minimum Cost to Make at Least One Valid Path in a Grid
Minimum Number of Lines to Cover Points

Key takeaways

Min-cost flow: send a required flow at minimum total cost; reverse arcs have negative cost.
Successive shortest paths augments along the cheapest residual path; path costs never decrease.
Potentials make every reduced cost non-negative so Dijkstra replaces Bellman-Ford.