min-cost max-flow
Plain max flow asks only how much you can ship. But often each pipe also has a price per unit shipped, and among all the ways to ship the maximum amount you want the cheapest. Or you fix a target amount to ship and minimize its cost. Min-cost max-flow answers exactly this: push the most flow possible, and of all maximum flows, find one of least total cost.
The setup adds a cost a(u, v) per unit of flow to each edge, alongside its capacity. The cost of a flow f is the sum over edges of a(u, v) * f(u, v), and the goal is a maximum-value flow that minimizes this sum (or a flow of a given target value with minimum cost). The key tool is the successive-shortest-paths method: repeatedly find a minimum-cost (cheapest, not shortest-in-edges) augmenting path in the residual graph and push along it. The residual graph must carry costs too — a backward residual edge has cost minus a(u, v), since canceling flow refunds its price. Because edge costs can be negative (those backward edges), you find the cheapest augmenting path with Bellman-Ford, or with Dijkstra after a potential reweighting (Johnson's technique) to keep all reduced costs nonnegative. A clean invariant makes it correct: if you always augment along a cheapest path, the flow stays a minimum-cost flow for its current value, so the final maximum flow is also minimum-cost.
Min-cost max-flow is the workhorse for assignment-with-costs problems: the assignment problem (match workers to jobs minimizing total cost), transportation and logistics, and many scheduling problems where you both want maximum throughput and care about a price. It generalizes both shortest paths (a single cheapest unit of flow) and max flow (ignore costs). The honest caveats: it is heavier than plain max flow — successive shortest paths runs in roughly O(V * E * f) or, with potentials, O(f * (E + V log V)) per unit-value style bounds, so very large flow values hurt — and you must use a method that tolerates the negative-cost backward edges, which is why naive Dijkstra alone is not enough.
Two routes from s to t both have capacity 1: route 1 costs 5 per unit, route 2 costs 8. To ship 1 unit, min-cost max-flow picks route 1 (cost 5). To ship 2 units (the max), it must use both, total cost 13 — there is no cheaper way to move 2 units, even though route 2 alone is pricier.
Augment along cheapest paths first; the running minimum-cost invariant makes the final maximum flow least-cost too.
Backward residual edges have negative cost, so you cannot use plain Dijkstra to find the cheapest augmenting path — use Bellman-Ford, or Dijkstra with Johnson-style potentials. And cost grows with the flow value, so large target flows can be slow.