The Cheapest Flow

A company needs to ship goods from a warehouse to a city through a network of roads, each with a capacity (how much it can carry) and a cost (price per unit). You must move a fixed amount — the demand — and you want to do it as cheaply as possible.

The naive instinct is to dump everything onto the cheapest road. But the cheapest road has limited capacity; once it's full, the overflow must take pricier routes. Balancing cost against capacity across the whole network is the real puzzle.

That's minimum-cost flow, and it's a quiet hero. Unlike most problems on this site, it's easy — solvable in polynomial time. Better still, it's a unifier: maximum flow, shortest paths, and the assignment problem are all special cases of it. One efficient algorithm, a whole family of problems solved.

Try it. You must ship 4 units from source to sink. Three routes are available, each with a capacity and a cost per unit. Use the +/− buttons to split your shipment across them so the total flow is 4 — and the total cost is as low as possible.

<p class="hint">{{hint}}</p>
<div id="routes" class="routes"></div>
<div class="meter">
  <div>{{shipped_label}} <b id="ship">0</b> / 4</div>
  <div>{{total_cost_label}} <b id="cost" class="cost">0</b></div>
  <div id="status" class="status"></div>
</div>
<div class="btns">
  <button id="opt" type="button">{{btn_optimize}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.routes { display: flex; flex-direction: column; gap: .6rem; margin-bottom: 1rem; }
.route { border: 1px solid #e2e6eb; border-radius: 10px; padding: .6rem .8rem; display: flex; align-items: center; gap: .8rem; flex-wrap: wrap; }
.rname { font: 800 14px system-ui; color: #1d3557; min-width: 70px; }
.rinfo { font: 600 12.5px system-ui; color: #777; flex: 1; min-width: 120px; }
.ctrl { display: flex; align-items: center; gap: .4rem; }
.ctrl button { width: 30px; height: 30px; padding: 0; font: 800 16px system-ui; }
.fval { font: 800 18px ui-monospace, monospace; color: #2a9d8f; min-width: 1.6rem; text-align: center; }
.bar { height: 8px; background: #eef1f4; border-radius: 4px; overflow: hidden; flex-basis: 100%; margin-top: .3rem; }
.bar .fill { height: 100%; background: #2a9d8f; }
.meter { display: flex; gap: 1.3rem; align-items: center; margin-bottom: .6rem; font-size: 1rem; flex-wrap: wrap; }
.meter b { color: #1d3557; font-family: ui-monospace, monospace; }
.cost { color: #457b9d !important; }
.status { font-weight: 800; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

// Code not found

Fill the cheap route first, but it caps out — so you spill into pricier ones. Hit Optimize for the cheapest feasible plan. It's the everyday tension of logistics: the lowest-cost edges are exactly the ones that run out of room first.

Minimum-cost flow is one of the great well-solved problems:

• Checking is easy. Verify flow conservation, capacities, and total demand, then sum the costs.
• It's polynomial. Classic algorithms — successive shortest paths, cycle-canceling, cost-scaling, and the very practical network simplex — find the exact optimum efficiently.
• Integer in, integer out. If capacities and demands are integers, an optimal flow with integer values always exists — no awkward fractions, unlike general integer programming.
• It unifies a family. Set the costs to zero and you get maximum flow. Set capacities to one with unit costs and you get shortest paths. Frame it on a bipartite graph and you get the assignment problem. One model, many classics.
• Getting faster. Recent breakthroughs put min-cost flow within reach of near-linear time — a headline result in modern algorithms research.

So this is a corner of the map firmly in the easy, conquered territory — and a remarkably useful one.

Minimum-cost flow quietly optimizes the movement of almost everything:

• Logistics and supply chains: shipping goods from factories to stores at least cost.
• Transportation: routing vehicles, freight and even passengers across networks.
• Telecom and data: sending traffic over links with bandwidth limits and costs.
• Scheduling and assignment: matching workers, machines or tasks (as a flow problem).
• Image processing and vision: surprisingly, segmentation and matching map to min-cost flow.

Because it's exact, fast, and so general, it's a workhorse inside operations-research toolkits everywhere.

Minimum-cost flow is a reminder that easy doesn't mean trivial. It's solvable in polynomial time, yet it's powerful enough to swallow three of the classics — max-flow, shortest paths, and assignment — as special cases. Learn to solve it once, and a whole shelf of logistics, routing and matching problems falls into place.

Among a site full of NP-hard walls and undecidable ceilings, it's a satisfying high point: a genuinely useful, genuinely hard-sounding problem that the field simply solved — exactly, efficiently, and beautifully. Every optimized shipment and routed packet is a small dividend of that victory.