Introduction

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.

Route the Flow

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">Ship <b>4 units</b> from source to sink. Split them across three routes (each with a <b>capacity</b> and a <b>cost per unit</b>) with the +/− buttons. Reach 4 units at the lowest total cost.</p>
<div id="routes" class="routes"></div>
<div class="meter">
  <div>Shipped: <b id="ship">0</b> / 4</div>
  <div>Total cost: <b id="cost" class="cost">0</b></div>
  <div id="status" class="status"></div>
</div>
<div class="btns">
  <button id="opt" type="button">Optimize</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Minimum-cost flow (here a simple parallel-route version, polynomial-time).
// Ship the demand across routes with capacities and unit costs at least total
// cost. Cheapest routes fill first but run out — Optimize finds the cheapest plan.
const DEMAND = 4;
const ROUTES = [
  { name: 'Route A', cap: 2, cost: 1 },
  { name: 'Route B', cap: 2, cost: 3 },
  { name: 'Route C', cap: 3, cost: 4 }
];
let flow = ROUTES.map(() => 0);

function totalShip() { return flow.reduce((a, b) => a + b, 0); }
function totalCost() { return flow.reduce((a, f, i) => a + f * ROUTES[i].cost, 0); }

// optimum: greedily fill by cheapest cost (optimal for parallel routes)
function optimum() {
  const order = ROUTES.map((r, i) => i).sort((a, b) => ROUTES[a].cost - ROUTES[b].cost);
  const f = ROUTES.map(() => 0); let need = DEMAND;
  for (const i of order) { const take = Math.min(ROUTES[i].cap, need); f[i] = take; need -= take; }
  return f;
}
const OPT = optimum(); const OPTCOST = OPT.reduce((a, f, i) => a + f * ROUTES[i].cost, 0);

function render() {
  document.getElementById('routes').innerHTML = ROUTES.map((r, i) =>
    fmt('<div class="route"><span class="rname">%name%</span><span class="rinfo">capacity %cap% · $%cost%/unit</span><span class="ctrl"><button data-d="-1" data-i="%i%">−</button><span class="fval">%v%</span><button data-d="1" data-i="%i%">+</button></span><div class="bar"><div class="fill" style="width:%v2%%"></div></div></div>', { name: r.name, cap: r.cap, cost: r.cost, i: i, v: flow[i], v2: flow[i] / r.cap * 100 })).join('');
  document.querySelectorAll('.ctrl button').forEach(b => b.addEventListener('click', () => {
    const i = +b.dataset.i, d = +b.dataset.d;
    const nf = flow[i] + d;
    if (nf < 0 || nf > ROUTES[i].cap) return;
    if (d > 0 && totalShip() >= DEMAND) return;
    flow[i] = nf; render();
  }));
  document.getElementById('ship').textContent = totalShip();
  document.getElementById('cost').textContent = '


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.

 + totalCost();
  const st = document.getElementById('status');
  if (totalShip() < DEMAND) { st.style.color = '#777'; st.textContent = fmt('Ship %v% more unit(s).', { v: DEMAND - totalShip() }); }
  else if (totalCost() <= OPTCOST) { st.style.color = '#0a7d33'; st.textContent = fmt('✓ Cheapest plan! ($%OPTCOST%)', { OPTCOST: OPTCOST }); }
  else { st.style.color = '#b9770e'; st.textContent = fmt('Done, but $ $%v% over the optimum ($%OPTCOST%).', { v: totalCost() - OPTCOST, OPTCOST: OPTCOST }); }
}

document.getElementById('opt').addEventListener('click', () => { flow = OPT.slice(); render(); });
document.getElementById('reset').addEventListener('click', () => { flow = ROUTES.map(() => 0); render(); });
render();
Result
Console

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.

The Good News

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/min-cost-flow/Content licensed under CC BY-NC 4.0.