Max-flow finds how much you can push from a source to a sink through capacitated pipes. Min-cost max-flow adds a twist: each edge also has a per-unit cost, and among all the ways to achieve the maximum flow, you want the one that costs the least. The elegant method is a small change to max-flow: instead of augmenting along any path with spare capacity, always augment along the cheapest one — a shortest path by cost in the residual graph. Because you always send flow the cheapest available way, the running total stays minimal at every step. Push flow and watch it fill the cheapest routes first.
max flow at minimum total cost · augment along the shortest-by-cost residual path each round
capacity / cost
Each edge carries up to its capacity, charging its cost per unit of flow.
residual graph
Remaining capacity forward, plus reverse edges (with negated cost) to undo flow.
cheapest path
A shortest path from source to sink measured by total cost (Bellman-Ford/SPFA).
augment
Push as much flow as the path’s bottleneck allows, along that cheapest path.
mcmf.js — shortest augmenting path, by cost
Ready
A flow network from S to T. Each edge shows flow / capacity and its per-unit cost. Each step finds the cheapest augmenting path and pushes flow along it. Augment to push.
0
total flow
0
total cost
0
paths pushed
How it works
The correctness rests on a clean invariant: if you only ever augment along a cheapest augmenting path, then after each augmentation the current flow is the minimum-cost flow of that value. So when you finally can’t augment any more (the max flow is reached), it is automatically the minimum-cost maximum flow. Finding the cheapest path needs care because the residual graph has negative-cost reverse edges (they let you “refund” previously sent flow), so a plain Dijkstra doesn’t directly apply — you use Bellman-Ford or its SPFA optimization (or Dijkstra with Johnson-style potentials to keep it fast). Push the bottleneck amount along that path, update forward and reverse residual capacities, and repeat.
1
Build the residual graph
For each edge with capacity c and cost w, keep a forward residual (spare capacity, cost +w) and a reverse residual (0 initial capacity, cost −w) so flow can be undone.
2
Find the cheapest augmenting path
Run a shortest-path by cost from source to sink over edges with spare capacity, using Bellman-Ford / SPFA (negative reverse-edge costs rule out plain Dijkstra unless you use potentials).
3
Augment along it
Send as much flow as the path’s minimum residual capacity (its bottleneck) allows. Add the flow forward and subtract it on the reverse residual edges.
✓
Repeat until no path remains
Keep augmenting along cheapest paths until none exists. Because each augmentation was cheapest-possible, the final maximum flow has minimum total cost.
Finds
max flow, min cost
Each round
cheapest path
Path search
Bellman-Ford/SPFA
Reverse edges
cost −w
The code
# min-cost max-flow: augment along cheapest pathswhile True:
dist, parent = spfa(source) # shortest path by COSTif dist[sink] == INF: break# no augmenting path left
push = min(residual[e] for e in path_to(sink)) # bottleneckfor e in path_to(sink):
residual[e] -= push # use capacity forward
residual[reverse(e)] += push # allow undo, cost is negated
max_flow += push
min_cost += push * dist[sink] # cheapest path's cost per unit
Quick check
1. How does min-cost max-flow differ from plain max-flow?
It reaches the same maximum flow value, but among all ways to do so it minimizes total cost. The mechanism: at each step, augment along the cheapest (shortest-by-cost) augmenting path instead of any path.
2. Why can’t you use plain Dijkstra to find the cheapest augmenting path?
Reverse residual edges carry negated cost (−w) so flow can be refunded. Negative edge costs break plain Dijkstra, so you use Bellman-Ford / SPFA, or Dijkstra with Johnson-style potentials to stay fast.
3. Why is the final flow guaranteed to be minimum cost?
There’s an invariant: if every augmentation uses a cheapest path, the current flow is the min-cost flow of that value. When you can no longer augment (max flow reached), it is therefore the min-cost maximum flow.
FAQ
What is min-cost max-flow?
A network-flow problem where each edge has a capacity and a per-unit cost; the goal is maximum flow from source to sink at minimum total cost. The standard method repeatedly finds the cheapest augmenting path (shortest by cost in the residual graph) and pushes flow along it, keeping the cost minimal at every step.
Why must the cheapest path search handle negative edges?
The residual graph’s reverse edges carry negated cost (they let you cancel and re-route earlier flow), which is essential but breaks plain Dijkstra. Implementations use Bellman-Ford, SPFA, or Dijkstra with node potentials (Johnson’s technique) to handle them efficiently.
What is min-cost max-flow used for?
Transportation and logistics (ship goods at least cost), assignment and scheduling (bipartite flow), network routing with congestion costs, image segmentation, and many operations-research problems — anything shaped like "route as much as possible, as cheaply as possible, under capacities."
How does it relate to the assignment problem?
The assignment problem (match n workers to n tasks at minimum cost) is a special case: a bipartite source→workers→tasks→sink graph with unit capacities, solved by a min-cost flow of value n. The Hungarian algorithm is a faster specialized method for that case.
SOLVE IT YOURSELF
Solve it: ship the most, for the least
Max-flow asks how much fits. Min-cost max-flow asks the follow-up every real system cares about: of all the ways to push that much, which is cheapest? Same residual graph — but you pick augmenting paths by price, not by whatever you find first. Python or TypeScript.
YOUR TASK
Implement MinCostMaxFlow with add_edge(u, v, cap, cost) (addEdge) and flow(s, t) returning (total_flow, total_cost). Cost is per unit shipped.
HINTS — 8 IDEAS
Store each edge with a paired reverse edge of zero capacity and negated cost. Pushing flow back later must refund what it charged.
Repeatedly find the cheapest source-to-sink path in the residual graph, push as much as its tightest edge allows, and repeat until no path remains.
Choosing by cost rather than by arbitrary discovery is the entire difference from plain max-flow. The final flow value is identical; the bill is not.
Those negative reverse costs are why you cannot just use Dijkstra here — it assumes non-negative weights. Bellman-Ford (or its SPFA queue form) handles them.
The bottleneck is the smallest residual capacity along the path. Push exactly that: any more overflows an edge, any less wastes an iteration.
Augmenting adds the pushed amount to each reverse edge as it subtracts from the forward one. That is what lets a later, cheaper route undo an earlier commitment.
Add bottleneck × path_cost to the bill each round — not the path cost once.
Because every round augments along a cheapest path, the running total is optimal at every flow value, not only at the end.