Introduction

Imagine a gas pipeline network, a shipping company, or a city's water grid. At each junction, supply arrives and demand leaves. Pipes have capacity limits and per-unit transport costs. The question is always the same: how do you route the flow to meet all demands at minimum total cost?

This is the minimum-cost flow problem, one of the most fundamental in combinatorial optimization. You can write it as a linear program, feed it to a general LP solver, and get the right answer โ€” but it's slow. LP solvers don't know you're on a graph.

The network simplex method does. Instead of pivoting arbitrary LP columns, it maintains a spanning tree of the network as its basis. Each pivot swaps exactly one edge in and one edge out of the tree โ€” a move that takes O(n)O(n) time instead of O(n3)O(n^{3}). In practice, the method often solves million-edge networks in a fraction of a second, making it the algorithm of choice in logistics, operations research, and infrastructure planning.

The result is exact (no approximation) and proven correct โ€” a rare combination of mathematical elegance and engineering speed.

Watch the Tree Pivot

Below is a small supply-and-demand network. Green nodes are sources (positive supply), red nodes are sinks (positive demand), and the edges carry unit costs. The thick blue edges form the current spanning tree basis.

<p class="hint">A supply-demand network with edge costs. <b>Blue edges</b> form the spanning-tree basis. Press <b>Next pivot</b> to run one step of network simplex โ€” it finds a negative-reduced-cost arc, adds it to the tree, and removes one arc from the resulting cycle.</p>
<canvas id="canvas" width="420" height="265"></canvas>
<div class="info" id="info">Reduced costs shown on dashed non-tree edges. Red = negative (can improve).</div>
<div class="btns">
  <button id="pivot" type="button">Next pivot</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="legend">
  <span class="leg-item"><span class="dot supply"></span> Supply (+3)</span>
  <span class="leg-item"><span class="dot demand"></span> Demand (โˆ’3)</span>
  <span class="leg-item"><span class="dot neutral"></span> Transit (0)</span>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .55rem; line-height: 1.45; }
canvas { display: block; border-radius: 10px; background: #f4f7fa;
         border: 1px solid #dce3ea; max-width: 100%; }
.info { font-size: .88rem; font-weight: 600; margin: .45rem 0; min-height: 1.3em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 14px system-ui; padding: .42rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .42; cursor: default; }
.legend { display: flex; gap: .9rem; flex-wrap: wrap; font-size: .8rem; color: #555; }
.leg-item { display: flex; align-items: center; gap: .3rem; }
.dot { width: 11px; height: 11px; border-radius: 50%; display: inline-block; border: 1.5px solid #888; }
.dot.supply { background: #2e7d32; border-color: #1b5e20; }
.dot.demand  { background: #c62828; border-color: #7f0000; }
.dot.neutral { background: #e8eef3; border-color: #8898a9; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Network simplex demo โ€” 5-node min-cost flow instance.
// Nodes: S(supply=3), A(transit), B(transit), C(transit), T(demand=3).
// Initial spanning tree routes all flow through the expensive Sโ†’Aโ†’Cโ†’T path (cost 15).
// Two pivots bring it to the optimal Sโ†’Bโ†’Cโ†’T path (cost 12).

// โ”€โ”€ Graph โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const NODES = [
  { id:0, label:'S', b:3,  x:52,  y:132, type:'supply'  },
  { id:1, label:'A', b:0,  x:165, y:55,  type:'neutral' },
  { id:2, label:'B', b:0,  x:165, y:210, type:'neutral' },
  { id:3, label:'C', b:0,  x:290, y:132, type:'neutral' },
  { id:4, label:'T', b:-3, x:385, y:132, type:'demand'  }
];
// 6 directed arcs with capacities and costs
const ARCS = [
  { from:0, to:1, cap:5, cost:3 },  // 0: Sโ†’A  cost 3
  { from:0, to:2, cap:5, cost:1 },  // 1: Sโ†’B  cost 1
  { from:1, to:3, cap:5, cost:1 },  // 2: Aโ†’C  cost 1
  { from:2, to:3, cap:5, cost:2 },  // 3: Bโ†’C  cost 2
  { from:1, to:2, cap:5, cost:3 },  // 4: Aโ†’B  cost 3
  { from:3, to:4, cap:5, cost:1 },  // 5: Cโ†’T  cost 1
];

// โ”€โ”€ State โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let treeSet, flow, optimal, pivotCount;

function initState() {
  // Initial tree: {0,2,4,5} Sโ†’A, Aโ†’C, Aโ†’B(leaf), Cโ†’T
  // feasible flow: 3 units on Sโ†’Aโ†’Cโ†’T, 0 elsewhere; cost = 3*3+3*1+3*1 = 15
  treeSet = new Set([0, 2, 4, 5]);
  flow = [3, 0, 3, 0, 0, 3];
  optimal = false;
  pivotCount = 0;
}

// โ”€โ”€ Dual: node potentials from spanning tree โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// For each tree arc (iโ†’j): reduced_cost = cost - ฯ€[i] + ฯ€[j] = 0
// So ฯ€[j] = ฯ€[i] - cost. Set ฯ€[root=0] = 0 and propagate.
function computePotentials() {
  const pi = new Array(NODES.length).fill(null);
  pi[0] = 0;
  let changed = true;
  while (changed) {
    changed = false;
    for (const ei of treeSet) {
      const e = ARCS[ei];
      if (pi[e.from] !== null && pi[e.to] === null) { pi[e.to] = pi[e.from] - e.cost; changed = true; }
      if (pi[e.to] !== null && pi[e.from] === null) { pi[e.from] = pi[e.to] + e.cost; changed = true; }
    }
  }
  return pi;
}

// Reduced cost of arc ei: cฬƒ = cost - ฯ€[from] + ฯ€[to]
function rc(ei, pi) { const e = ARCS[ei]; return e.cost - pi[e.from] + pi[e.to]; }

function totalCost() { return ARCS.reduce((s, e, i) => s + e.cost * flow[i], 0); }

// โ”€โ”€ Pivot โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// 1. Find non-tree arc with most-negative reduced cost (entering arc).
// 2. Add it to tree โ†’ creates exactly one cycle.
// 3. Find cycle via BFS in the tree.
// 4. Send as much flow as possible around the cycle.
// 5. The arc that hits its bound (capacity or 0) leaves the tree.
function pivot() {
  const pi = computePotentials();

  // Entering arc: most-negative reduced cost
  let enterIdx = -1, bestRC = 0;
  for (let ei = 0; ei < ARCS.length; ei++) {
    if (treeSet.has(ei)) continue;
    const r = rc(ei, pi);
    if (r < bestRC) { bestRC = r; enterIdx = ei; }
  }
  if (enterIdx === -1) { optimal = true; return null; }

  const enter = ARCS[enterIdx];

  // BFS tree to find path from enter.from to enter.to
  const adj = Array.from({ length: NODES.length }, () => []);
  for (const ei of treeSet) {
    const e = ARCS[ei];
    adj[e.from].push({ node: e.to, ei, fwd: true  });
    adj[e.to  ].push({ node: e.from, ei, fwd: false });
  }
  const parent = new Array(NODES.length).fill(null);
  const visited = new Array(NODES.length).fill(false);
  const queue = [enter.from]; visited[enter.from] = true;
  let found = false;
  while (queue.length && !found) {
    const u = queue.shift();
    for (const { node: v, ei, fwd } of adj[u]) {
      if (!visited[v]) {
        visited[v] = true;
        parent[v] = { node: u, ei, fwd };
        if (v === enter.to) { found = true; break; }
        queue.push(v);
      }
    }
  }

  // Build cycle: trace path from enter.to back to enter.from (direction reversed)
  // parent[v]={node:u, fwd:true} means tree arc goes uโ†’v, so cycle goes vโ†’u (reversed)
  const cycle = [];
  let cur = enter.to;
  while (cur !== enter.from) {
    const p = parent[cur];
    cycle.push({ ei: p.ei, fwd: !p.fwd }); // reverse direction for return path
    cur = p.node;
  }
  cycle.push({ ei: enterIdx, fwd: true }); // entering arc closes the cycle forward

  // Max flow delta = min residual capacity around cycle
  // fwd arc: residual = cap - flow; rev arc: residual = flow
  let delta = Infinity, leaveIdx = -1;
  for (const { ei, fwd } of cycle) {
    if (ei === enterIdx) continue;
    const residual = fwd ? (ARCS[ei].cap - flow[ei]) : flow[ei];
    if (residual < delta) { delta = residual; leaveIdx = ei; }
  }
  if (delta === Infinity || leaveIdx === -1) { optimal = true; return null; } // degenerate guard

  // Update flows
  for (const { ei, fwd } of cycle) {
    if (fwd) flow[ei] += delta; else flow[ei] -= delta;
  }

  // Swap tree arcs
  treeSet.delete(leaveIdx);
  treeSet.add(enterIdx);
  pivotCount++;

  return {
    enterIdx, leaveIdx, delta, rc: bestRC,
    enterName: NODES[enter.from].label + 'โ†’' + NODES[enter.to].label,
    leaveName: NODES[ARCS[leaveIdx].from].label + 'โ†’' + NODES[ARCS[leaveIdx].to].label
  };
}

// โ”€โ”€ Canvas drawing โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const canvas = document.getElementById('canvas');
const ctx    = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

// Slight per-arc offset so parallel edges don't overlap
const ARC_OFFSET = [0, 18, 0, -18, 0, 0]; // px perpendicular offset per arc

function arrowHead(x1, y1, x2, y2, color) {
  const dx = x2 - x1, dy = y2 - y1;
  const len = Math.sqrt(dx*dx + dy*dy);
  const ux = dx/len, uy = dy/len;
  const px = -uy, py = ux;
  const tip = { x: x2 - ux*16, y: y2 - uy*16 };
  ctx.beginPath();
  ctx.moveTo(tip.x - ux*2 + px*5, tip.y - uy*2 + py*5);
  ctx.lineTo(tip.x + ux*4, tip.y + uy*4);
  ctx.lineTo(tip.x - ux*2 - px*5, tip.y - uy*2 - py*5);
  ctx.closePath();
  ctx.fillStyle = color;
  ctx.fill();
}

function draw() {
  ctx.clearRect(0, 0, W, H);
  const pi = computePotentials();

  // Draw arcs
  for (let ei = 0; ei < ARCS.length; ei++) {
    const e = ARCS[ei];
    const fn = NODES[e.from], tn = NODES[e.to];
    const inTree = treeSet.has(ei);
    const rCost  = rc(ei, pi);
    const off    = ARC_OFFSET[ei];

    // Perpendicular offset
    const dx = tn.x - fn.x, dy = tn.y - fn.y;
    const len = Math.sqrt(dx*dx + dy*dy);
    const ox = -dy/len * off, oy = dx/len * off;

    const x1 = fn.x + ox, y1 = fn.y + oy;
    const x2 = tn.x + ox, y2 = tn.y + oy;

    const color = inTree ? '#1565c0' : (rCost < 0 ? '#c62828' : '#9aaebc');

    ctx.beginPath();
    ctx.moveTo(x1, y1);
    ctx.lineTo(x2, y2);
    ctx.lineWidth   = inTree ? 2.8 : 1.6;
    ctx.strokeStyle = color;
    ctx.setLineDash(inTree ? [] : [5, 4]);
    ctx.stroke();
    ctx.setLineDash([]);

    arrowHead(x1, y1, x2, y2, color);

    // Label: cost (and flow for tree arcs, reduced cost for non-tree)
    const mx = (x1 + x2)/2, my = (y1 + y2)/2;
    const lx = mx + (-dy/len)*12, ly = my + (dx/len)*12; // push label sideways
    ctx.font = '10.5px ui-monospace, monospace';
    ctx.fillStyle = inTree ? '#0d47a1' : (rCost < 0 ? '#b71c1c' : '#546e7a');
    const lbl = inTree ? `c${e.cost} f${flow[ei]}` : `c${e.cost} r${rCost}`;
    ctx.textAlign = 'center';
    ctx.fillText(lbl, lx, ly);
  }
  ctx.textAlign = 'left';

  // Draw nodes
  for (const n of NODES) {
    ctx.beginPath();
    ctx.arc(n.x, n.y, 19, 0, 2*Math.PI);
    ctx.fillStyle   = n.type==='supply' ? '#2e7d32' : n.type==='demand' ? '#c62828' : '#e8eef3';
    ctx.fill();
    ctx.strokeStyle = n.type==='supply' ? '#1b5e20' : n.type==='demand' ? '#7f0000' : '#8898a9';
    ctx.lineWidth = 2;
    ctx.stroke();

    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.font = 'bold 13px system-ui';
    ctx.fillStyle = n.type==='neutral' ? '#1d3557' : '#fff';
    ctx.fillText(n.label, n.x, n.y - 2);
    ctx.font = '10px system-ui';
    ctx.fillStyle = n.type==='neutral' ? '#78909c' : '#cfd8dc';
    ctx.fillText((n.b > 0 ? '+' : '') + n.b, n.x, n.y + 8);
  }
  ctx.textAlign = 'left';
  ctx.textBaseline = 'alphabetic';
}

// โ”€โ”€ UI โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const info     = document.getElementById('info');
const pivotBtn = document.getElementById('pivot');

function setInfo(msg) { info.textContent = msg; }

pivotBtn.addEventListener('click', () => {
  const result = pivot();
  draw();
  if (!result) {
    setInfo(fmt('Optimal! All reduced costs โ‰ฅ 0. Total cost = %totalCost% after %pivotCount% pivot(s).', { totalCost: totalCost(), pivotCount: pivotCount }));
    pivotBtn.disabled = true;
  } else {
    const degStr = result.delta === 0 ? ' (degenerate pivot, ฮ”=0)' : '';
    setInfo(fmt('Pivot %pivotCount%: arc %enterName% IN,, arc %leaveName% OUT (ฮ”=%delta%, rc=%rc%)%degStr%. Cost = %totalCost%.', { pivotCount: pivotCount, enterName: result.enterName, leaveName: result.leaveName, delta: result.delta, rc: result.rc, degStr: degStr, totalCost: totalCost() }));
  }
});

document.getElementById('reset').addEventListener('click', () => {
  initState();
  pivotBtn.disabled = false;
  setInfo('Reduced costs shown on dashed non-tree edges. Red = negative (can improve).');
  draw();
});

// โ”€โ”€ Boot & verification โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
initState();
draw();

// Verify algorithm offline: run to completion, check optimal cost = 12
(function verify() {
  const savedTree = new Set(treeSet);
  const savedFlow = [...flow];
  const savedOptimal = optimal;
  const savedPivotCount = pivotCount;

  initState();
  let steps = 0;
  while (steps < 20) {
    const r = pivot();
    if (!r) break;
    steps++;
  }
  const optCost = totalCost();
  // Optimal: route all 3 units via Sโ†’Bโ†’Cโ†’T at cost 1+2+1=4/unit โ†’ total 12
  console.assert(optCost === 12, fmt('Optimal cost should be 12, got %optCost%', { optCost: optCost }));
  console.assert(optimal === true, 'Should have reached optimal');
  console.log('Verification: optimal cost =', optCost, '(expected 12) after', steps, 'pivots โœ“');

  // Restore initial display state
  treeSet = savedTree;
  flow = savedFlow;
  optimal = savedOptimal;
  pivotCount = savedPivotCount;
  draw();
})();
Result
Console

Press Next pivot to run one step of network simplex. Each step finds an arc not in the tree whose reduced cost is negative (meaning sending flow through it can save money), adds it to the tree, and removes the arc that leaves the resulting cycle. When every non-tree arc has a non-negative reduced cost the flow is optimal โ€” press Reset to start over.

The Real Complexity

Network simplex is a specialization of the simplex method (George Dantzig, 1947) that exploits one key insight: the basic feasible solutions of the min-cost flow LP correspond exactly to spanning trees of the underlying graph.

  • Each basis = a spanning tree. In any basic feasible solution, the flow is uniquely determined by which nโˆ’1n-1 edges form the basis. Non-tree edges carry either zero flow or their maximum capacity (at their lower/upper bounds).
  • Pivots are cheap. Adding a non-tree edge to the tree creates exactly one cycle. Sending as much flow as possible around that cycle (the cycle-canceling step) costs O(n)O(n) to find and O(n)O(n) to update. Compare this with the O(n3)O(n^{3}) cost of a general LP pivot.
  • Reduced costs guide the search. For each non-tree arc (i,j), the reduced cost c~ij=cijโˆ’ฯ€i+ฯ€j\tilde{c}_{ij} = c_{ij} - \pi_i + \pi_j, where ฯ€\pi are the node potentials (dual variables maintained on the tree). An arc with a negative reduced cost can improve the objective; choosing one and pivoting is a valid simplex step.
  • Termination and optimality. When no non-tree arc has a negative reduced cost, the current spanning tree solution is optimal by LP duality. Orlin (1997) proved a strongly polynomial bound of O(nmlogโก(nC))O(nm \log(nC)) pivots, where n = nodes, m = edges, C = max cost โ€” though in practice the method converges in far fewer steps.

The closest relative is min-cost flow solved by the successive shortest-paths algorithm, which is also polynomial but typically slower in practice. Network simplex dominates real-world benchmarks on transportation and assignment instances. Unlike linear programming in general, no exponential examples are known for typical network simplex implementations.

Where It Matters

Minimum-cost flow is a universal modeling language. If you can express a problem as "route flow on a graph at minimum cost," network simplex will solve it faster than almost anything else:

  • Transportation and logistics: shipping goods from warehouses to stores, routing trucks or planes, assigning drivers to shifts โ€” the classic transportation and assignment problems are special cases of min-cost flow.
  • Scheduling: job scheduling on machines and crew scheduling for airlines are naturally modeled as flow problems, and network simplex is the workhorse solver.
  • Image segmentation: graph-cut methods in computer vision reduce certain segmentation tasks to min-cut / max-flow (which is dual to min-cost flow), and network simplex implementations underpin fast solvers.
  • Operations research: facility-location, distribution planning, and supply-chain design all lean on min-cost flow sub-problems solved by network simplex.
  • Network design: telecommunications routing, power-grid load balancing, and water-distribution optimization are direct applications.

The algorithm is so practically efficient that LEMON (Library for Efficient Modeling and Optimization in Networks) and OR-Tools list it as the default solver for min-cost flow. If your problem fits the flow template, network simplex is almost certainly the right tool.

Conclusion

Network simplex is a textbook example of why exploiting problem structure pays off enormously. A naรฏve LP solver ignores the graph; network simplex bets everything on it โ€” and wins. By maintaining a spanning tree as the LP basis and pivoting one edge at a time, it turns an O(n3)O(n^{3})-per-pivot algorithm into an O(n)O(n)-per-pivot one.

The deeper lesson is one of the themes of linear programming: the geometry of a feasible polytope can be extremely special when the constraint matrix has structure. For network flow, that structure is so rich that an exact polynomial-time algorithm exists, and it's fast enough to route the flow of an entire country in milliseconds.

Next time you order something online and it arrives via an optimized shipping route, there's a good chance a spanning-tree pivot is responsible.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/network-simplex/Content licensed under CC BY-NC 4.0.