Min-Cost Max-Flow

Finding a maximum flow of minimum total cost by repeatedly augmenting along shortest-cost paths in the residual graph.

Cost on top of capacity

Min-cost max-flow (MCMF) adds a per-unit cost to each edge of a flow network and asks for a maximum flow whose total cost is smallest, or the cheapest flow of a required value. It generalizes both max flow and the assignment problem, and models transportation, scheduling, and matching with weights.

Successive shortest paths

Kronos motion — burner power flow

The standard method repeatedly finds the minimum-cost augmenting path from source to sink and pushes as much flow as its bottleneck allows. Because negative-cost residual edges appear, it uses Bellman-Ford or, with Johnson-style potentials, Dijkstra with reduced (non-negative) costs. Each augmentation preserves optimality of the current flow value, so the final flow is min-cost for its value.

Reduced costs with potentials

python

# reduced cost keeps Dijkstra applicable after the first pass
# rc(u,v) = cost(u,v) + h[u] - h[v]   where h is the potential
# after each Dijkstra, update:  h[v] += dist[v]
# push flow = min residual capacity along the shortest-cost path

Why potentials work

Johnson's potentials transform edge costs so that all reduced costs on residual edges are non-negative while preserving shortest paths. This lets Dijkstra replace Bellman-Ford after the first iteration, cutting each augmentation to O(E log V) and making MCMF practical on large graphs.

Uses

Weighted bipartite matching (the assignment problem) as unit-capacity MCMF.
Transportation and supply-demand balancing with shipping costs.
Scheduling and resource allocation with penalties.
Any problem expressible as cheapest routing of a required quantity.