Minimum-Cost Flow

The question

A courier firm moves parcels from its depot $s$ to a hub $t$ through three relay points $a$, $b$ and $c$. Each one-way link has a capacity (parcels per hour) and a cost per parcel:

s→a 4/1, s→b 1/6, a→b 4/2, a→t 4/7, b→c 1/3, b→t 2/2, c→a 3/6 (capacity/cost)

The firm must move 5 parcels an hour. That is also the most the network can carry: only $4+1=5$ can leave $s$. There are many ways to route five parcels, and they don't cost the same. Which is cheapest, and how would you convince an auditor that nothing cheaper exists?

This is minimum-cost flow: a network with capacities and a cost per unit on every edge, a demand $d$, and the task of sending $d$ units from $s$ to $t$ at the least total cost $\sum f(u,v)a(u,v)$, or reporting that $d$ units don't fit. The module assumes module 11 (flows, residual graphs, max-flow min-cut) and module 10 (Bellman–Ford and Dijkstra).

A maximum flow is not the answer

The obvious approach is to run a maximum-flow algorithm and stop. It returns some flow of value 5, but a max-flow algorithm never reads the costs, so nothing stops it from returning this one: 4 parcels on $s\to a\to t$, and 1 parcel that goes $s\to b\to c\to a\to t$, taking a detour through $c$ that doubles back to $a$. It is a valid flow of value 5, and it costs 51.

Brute force would find the cheapest: try every integer amount on every edge. Here that is $5·2·5·5·2·3·4=6000$ vectors, and the count is exponential in the number of edges.

from itertools import product

EDGES = [("s", "a", 4, 1), ("s", "b", 1, 6), ("a", "b", 4, 2), ("a", "t", 4, 7),
         ("b", "c", 1, 3), ("b", "t", 2, 2), ("c", "a", 3, 6)]   # (u, v, capacity, cost)
COST = {(u, v): c for u, v, _, c in EDGES}

def flow_cost(flow):
    return sum(f * e[3] for e, f in zip(EDGES, flow))

def cheapest_by_brute_force(d):
    """Try every integer flow vector; return the least cost of a flow of value d."""
    best, tried = None, 0
    for f in product(*[range(cap + 1) for _, _, cap, _ in EDGES]):
        tried += 1
        net = {v: 0 for v in "sabct"}
        for (u, v, _, _), x in zip(EDGES, f):
            net[u] -= x
            net[v] += x
        if net["t"] == d and net["a"] == net["b"] == net["c"] == 0:
            c = flow_cost(f)
            best = c if best is None or c < best else best
    return best, tried

WASTEFUL = [4, 1, 1, 4, 1, 1, 1]      # one parcel detours b -> c -> a
assert flow_cost(WASTEFUL) == 51
assert cheapest_by_brute_force(5) == (37, 6000)
assert cheapest_by_brute_force(6)[0] is None       # six parcels don't fit

The cheapest routing costs 37, and the wasteful one pays 14 more. The waste is in the detour: the parcel that goes $b\to c\to a$ pays $3+6$ to reach $a$, then $7$ more on $a\to t$, when $b$ had a direct link to $t$ at cost 2 with room to spare.

The model: residual arcs have prices

Module 11's residual graph says how a flow can change. For every edge $u\to v$ carrying $f(u,v)$ it has a forward arc $u\to v$ with room $c(u,v)-f(u,v)$ and a reverse arc $v\to u$ with room $f(u,v)$. Now the arcs get prices too:

• the forward arc costs $a(u,v)$ per unit, since sending more pays the edge's price;
• the reverse arc costs $-a(u,v)$ per unit: taking a unit back refunds what it cost.

So residual graphs have negative arcs even when every edge cost is positive. Pushing one unit around a cycle of residual arcs keeps every vertex balanced and the value unchanged, and it changes the total cost by exactly the cycle's cost. A cycle with negative cost is money left on the table.

Under the wasteful flow the reverse arcs are $a\to s$ ($-1$), $b\to s$ ($-6$), $b\to a$ ($-2$), $t\to a$ ($-7$), $c\to b$ ($-3$), $t\to b$ ($-2$) and $a\to c$ ($-6$), and two cycles are negative:

• $a\to c\to b\to a$ costs $-6-3-2=-11$;
• $a\to c\to b\to t\to a$ costs $-6-3+2-7=-14$.

The second one reads as a plan: take the detouring parcel back off $c\to a$ and $b\to c$, send it $b\to t$ instead, and remove one parcel from $a\to t$.

When is a flow cheapest?

Proof. If $G_f$ has a negative cycle, push its bottleneck $b>0$ (the least room on it) around it. Every vertex on the cycle gains and loses $b$, so conservation and the value hold, the rooms keep the flow within capacity, and the cost drops by $b$ times the cycle's cost. So $f$ was not the cheapest.

Conversely, suppose some flow $f^{*}$ of the same value is cheaper. The difference $f^{*}-f$, read edge by edge (a positive difference uses the forward arc, a negative one the reverse arc), is a circulation in $G_f$: at every vertex, including $s$ and $t$, as much enters as leaves, because both flows have the same value. A circulation splits into cycles of $G_f$. This is the standard decomposition lemma, which we use without proof: repeatedly follow arcs carrying some of the circulation until a vertex repeats, and remove that cycle. The costs of those cycles add up to $\text{cost}(f^{*})-\text{cost}(f)<0$, so at least one of them is negative. $◻$

The theorem gives the auditor a certificate. To prove a flow is cheapest you don't compare it with the 6000 vectors: you show that its residual graph has no negative cycle, which Bellman–Ford from a virtual source (joined to every vertex at cost 0) checks in $O(VE)$.

Canceling cycles

The theorem is also an algorithm. Start from any flow of value $d$ (a max-flow algorithm gives one), and while the residual graph has a negative cycle, push its bottleneck around it. On the courier network one cancellation of the $-14$ cycle, with bottleneck 1, turns 51 into 37:

a, b, c, t = "a", "b", "c", "t"
cycle = [(a, c, -COST[(c, a)]), (c, b, -COST[(b, c)]), (b, t, COST[(b, t)]), (t, a, -COST[(a, t)])]
assert sum(price for _, _, price in cycle) == -14
assert -COST[(c, a)] - COST[(b, c)] - COST[(a, b)] == -11     # the other negative cycle

after = list(WASTEFUL)
after[6] -= 1          # a -> c takes a unit back from c -> a
after[4] -= 1          # c -> b takes a unit back from b -> c
after[5] += 1          # b -> t sends one more
after[3] -= 1          # t -> a takes a unit back from a -> t
assert after == [4, 1, 1, 3, 0, 2, 0] and flow_cost(after) == 51 - 14 == 37

With integer capacities and costs each cancellation lowers the cost by at least 1, so the loop ends. How many cancellations it takes depends on the numbers, not only on the size of the network. The lab has you write the loop and watch the cost fall frame by frame.

Successive shortest paths

Canceling repairs a bad flow. The other classic method never builds one. Start from no flow and repeat one step: find the cheapest path from $s$ to $t$ in the residual graph and push as much along it as it holds (or as much as is still needed). Because refund arcs are negative, the cheapest path is found with Bellman–Ford, not Dijkstra, for now.

On the courier network, 5 parcels take three pushes:

The first push is limited by $b\to t$ (capacity 2), the second by $s\to a$ (2 of its 4 left). The third is the interesting one: $s\to a$ is now full, so the only way out of $s$ is $s\to b$, and from $b$ the path takes the refund arc $b\to a$ at $-2$. One of the two parcels that went $a\to b$ is taken back and sent $a\to t$, and the new parcel takes its place on $b\to t$. The result is the flow [4, 1, 1, 3, 0, 2, 0] at 37, the same one canceling found.

Two things stand out. The costs per parcel, 5, 5, 8, 8, 11, never decrease. And every intermediate flow is itself the cheapest of its value. The block below checks both against brute force, which here stands in for the proof that follows:

per_parcel = [5, 5, 8, 8, 11]
assert per_parcel == sorted(per_parcel)
assert [cheapest_by_brute_force(k)[0] for k in (1, 2, 3, 4, 5)] == [5, 10, 18, 26, 37]
assert [sum(per_parcel[:k]) for k in (1, 2, 3, 4, 5)] == [5, 10, 18, 26, 37]

Why the cheapest path keeps the certificate

The claim is that after every push, the residual graph has no negative cycle, so by the theorem the current flow is the cheapest of its value. It holds at the start: with no flow there are no reverse arcs, and every edge cost is at least 0.

Suppose it holds before a push, and let $\delta (v)$ be the cheapest cost from $s$ to $v$ in $G_f$. Cheapest costs satisfy the triangle inequality $\delta (v)\le \delta (u)+a(u,v)$ on every residual arc, which says that the reduced cost

$$a_{\delta }(u,v)=a(u,v)+\delta (u)-\delta (v)\ge 0.$$

Along the cheapest path to $t$ the inequality is tight, so each of its arcs has reduced cost exactly 0. Now push. Arcs off the path are unchanged. Arcs on the path may lose room or vanish. The only new arcs are reverses of path arcs, with reduced cost $-0=0$. So after the push every residual arc still has $a_{\delta }\ge 0$.

Finally, around any cycle the $\delta$ terms telescope: each $\delta (v)$ is added once, when the cycle leaves $v$, and subtracted once, when it enters. A cycle's cost equals its reduced cost, which is a sum of non-negative terms. No cycle is negative. $◻$

The step not to skip is the path being cheapest. Push along any other path and one of its arcs has positive reduced cost. Its reverse then has negative reduced cost, and a negative cycle can appear. The same argument shows why the per-parcel costs never fall. Distances measured in reduced costs are at least 0, so the next cheapest path costs at least the last $\delta (t)$.

delta = {"s": 0, "a": 4, "b": 6, "c": 9, "t": 11}
arcs = [("a", "s", -1), ("s", "b", 6), ("a", "b", 2), ("b", "a", -2), ("a", "t", 7),
        ("t", "a", -7), ("b", "c", 3), ("t", "b", -2), ("c", "a", 6)]   # residual arcs before push 3
reduced = {(u, v): cost + delta[u] - delta[v] for u, v, cost in arcs}
assert all(rc >= 0 for rc in reduced.values())
assert reduced[("s", "b")] == reduced[("b", "a")] == reduced[("a", "t")] == 0     # the path
loop = [("a", "b"), ("b", "c"), ("c", "a")]
assert sum(COST[e] for e in loop) == sum(reduced[e] for e in loop) == 11          # telescoping

Potentials: Dijkstra with negative arcs

Bellman–Ford costs up to $V-1$ rounds over all $2E$ residual arcs per search. Dijkstra would cost one pass, but it is wrong on negative arcs. The proof above suggests the way round it. Keep a number $\pi (v)$ for every vertex, called a potential, and search on reduced costs $a_{\pi }(u,v)=a(u,v)+\pi (u)-\pi (v)$ instead of real costs. Every $s$–$t$ path's reduced cost is its real cost plus $\pi (s)-\pi (t)$, the same constant for all of them, so the cheapest path doesn't change. If every reduced cost is at least 0, Dijkstra is exact.

Lemma (potentials). Suppose every residual arc has $a_{\pi }\ge 0$, and let ${\delta }_{\pi }$ be the Dijkstra distances from $s$ under those reduced costs. Then after the push along the path found, ${\pi }^{\prime }(v)=\pi (v)+min({\delta }_{\pi }(v),{\delta }_{\pi }(t))$ again gives every residual arc a reduced cost of at least 0. Proof: the same argument one level up. The reduced costs under ${\pi }^{\prime }$ are the reduced costs under $\pi$ re-reduced by $min({\delta }_{\pi },{\delta }_{\pi }(t))$. Capping a distance at a constant keeps the triangle inequality, so every old arc stays at 0 or more. Every vertex on the path has ${\delta }_{\pi }\le {\delta }_{\pi }(t)$, so the path's arcs stay tight and their new reverses get 0. The cap only matters for vertices the search never reached (${\delta }_{\pi }=\infty$). $◻$

With all edge costs at least 0, $\pi =0$ is a valid start. With some negative edge costs but no negative cycle, one Bellman–Ford pass supplies the first $\pi$, and every later search is a Dijkstra.

Cost

We count arc scans, with integer capacities and costs, in the worst case. Each push moves at least one unit, so there are at most $d$ pushes plus one failing search:

• with Bellman–Ford, $O(VE)$ per search, $O(d·VE)$ in all;
• with potentials and a binary-heap Dijkstra, $O(E\log V)$ per search, $O(d·E\log V)$.

Both are pseudo-polynomial: $d$ is a number in the input, not its size. Cycle canceling also terminates on integer data, but its count depends on the costs. Always canceling a cycle of least mean cost is polynomial in the size alone (Goldberg and Tarjan; cited, not proved here).

Assignment is a special case

Four workers, four jobs, and a cost for each worker–job pair:

Build a network: $s\to$ worker $i$ (capacity 1, cost 0), worker $i\to$ job $j$ (capacity 1, cost $C_{ij}$), job $j\to t$ (capacity 1, cost 0), and send $d=4$. Integer capacities give an integer cheapest flow, because every push moves a whole number of units, so each worker sends exactly one unit along exactly one pair. The cheapest flow is the cheapest assignment. It takes $n$ pushes of a Dijkstra over $n^2$ arcs: $O(n^3\log n)$. The Hungarian method, a specialised version of the same idea, runs in $O(n^3)$.

The greedy alternatives are cheaper to run and more expensive to follow. Giving each worker in turn their cheapest free job costs 17, and taking the cheapest free cells first costs 16:

from itertools import permutations

M = [[4, 1, 1, 6], [1, 7, 8, 7], [5, 9, 8, 8], [3, 2, 6, 7]]
costs = sorted((sum(M[i][p[i]] for i in range(4)), p) for p in permutations(range(4)))
assert costs[0] == (12, (2, 0, 3, 1)) and costs[1][0] > 12

used, row_greedy = set(), 0
for i in range(4):
    j = min((j for j in range(4) if j not in used), key=lambda j: (M[i][j], j))
    used.add(j)
    row_greedy += M[i][j]
rows, cols, cell_greedy = set(), set(), 0
for m, i, j in sorted((M[i][j], i, j) for i in range(4) for j in range(4)):
    if i not in rows and j not in cols:
        rows.add(i)
        cols.add(j)
        cell_greedy += m
assert (row_greedy, cell_greedy) == (17, 16)

Row greedy gives worker 0 job 1 (cost 1) and leaves workers 2 and 3 to pay 8 and 7. The residual graph of its answer has a negative cycle: rotate workers 0, 2 and 3 to jobs 2, 3 and 1, and the total falls by 5.

Measure the claim

The bound says one Dijkstra pass per search against up to $V-1$ Bellman–Ford rounds. Here are arc scans on random networks (about $6V$ edges, capacities 1–5, costs 1–20, seeds $451+V$), sending the maximum flow $d$ from vertex 0 to vertex $V-1$:

rows = [(30, 179, 16, 5728, 33652), (60, 347, 9, 6246, 42334), (120, 707, 13, 18382, 144228)]
assert [round(dij / pushes / (2 * E), 2) for V, E, pushes, dij, bf in rows] == [1.0, 1.0, 1.0]
assert [round(bf / pushes / (2 * E), 1) for V, E, pushes, dij, bf in rows] == [5.9, 6.8, 7.8]

Dijkstra scans each arc about once per push, exactly as the proof says. Bellman–Ford needs 6 to 8 rounds, far below its worst case of $V-1$ = 29, 59 and 119, because on these networks the cheapest paths have few arcs and the loop stops early when a round changes nothing. That is a measurement on these instances, not a guarantee. The gap still grows with $V$. Every push stayed within its bound, and there were never more pushes than $d$.

A problem that looks different

Three warehouses hold 40, 25 and 35 pallets. Four stores need 30, 20, 30 and 20. Shipping one pallet from warehouse $i$ to store $j$ costs a known amount, and each route can carry any number. What is the cheapest shipping plan? Nothing in it mentions paths or cycles. Where are the source, the sink and the capacities? The lab's last problem is a different one.

Practise

In the lab you give residual arcs their refund prices and cancel negative cycles on a new network, watching the cost fall in every frame; predict, then trace, successive shortest paths, refund arc included; write the version with potentials and Dijkstra, with a check that reads every frame and asserts that no reduced cost is negative, and solve an assignment with it; count arc scans for both searches on your own networks; and build a roster for a problem that doesn't say what it is.

Recap

You can now: price residual arcs (a reverse arc refunds); prove that a flow is the cheapest of its value exactly when its residual graph has no negative cycle; run successive shortest paths with Bellman–Ford, or with potentials and Dijkstra; repair a flow by canceling cycles; and solve assignment as a special case.

Invariant: after every push along a cheapest residual path, every residual arc has reduced cost at least 0, so no cycle is negative and the flow is the cheapest of its value.

Complexity achieved: $O(d·E\log V)$ with potentials, against $O(d·VE)$ with Bellman–Ford, integer data, worst case. Trying every integer flow is exponential in the number of edges.

Failure mode: reverse arcs priced at $+a$ instead of $-a$. The code runs and returns a flow that is not the cheapest (here 51 would pass for optimal).

In real software: Google OR-Tools provides SimpleMinCostFlow and SimpleLinearSumAssignment; SciPy's scipy.optimize.linear_sum_assignment solves the assignment problem; NetworkX offers min_cost_flow and network_simplex.

Retrieval (module 10): cycle canceling needs a negative cycle in the residual graph. How could Floyd–Warshall find one, and what would it cost against Bellman–Ford?

Check yourself

1. Why does pushing along a cheapest path keep the residual graph free of negative cycles? What goes wrong with a path that is not the cheapest?
2. Give $a\to b$ a cost of $-3$ and leave the rest of the courier network alone. What changes in how you start, and what does the cheapest routing of 5 parcels cost now?
3. On the 4 × 4 matrix, compare row greedy, cheapest-cell greedy and minimum-cost flow. Which residual cycle shows that row greedy's answer is not the cheapest?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.