Vibe Engines Learn
Algorithms · Graphs

Cheapest Flow First.

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 paths while True: dist, parent = spfa(source) # shortest path by COST if dist[sink] == INF: break # no augmenting path left push = min(residual[e] for e in path_to(sink)) # bottleneck for 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?

2. Why can’t you use plain Dijkstra to find the cheapest augmenting path?

3. Why is the final flow guaranteed to be minimum cost?

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.

Keep going

Algorithm

Dinic's Max-Flow →
Algorithm

Bellman-Ford →
Algorithm

Dijkstra's Last Mile →
Roadmap

The DSA Roadmap →
Finished this one? 0 / 98 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →