Edmonds-Karp, Dinic's, and push-relabel all answer the same question — how much can this network carry? — and none of them care how it gets carried. Give every edge a capacity and a cost per unit, and a new question opens up: among every flow that achieves the maximum value, which one is cheapest? That's a different kind of "best" than Hungarian Algorithm finds — Hungarian solves cost-weighted matching (every worker to exactly one job) — while this is cost-weighted flow along a general network, where one edge can carry any amount up to its capacity.
The fix reuses Edmonds-Karp's own machine almost unchanged: repeatedly find an augmenting path in the residual graph, push flow equal to its bottleneck, repeat. The only change is which path — instead of the shortest by hop count (BFS), always take the cheapest by total cost. That one substitution has a real consequence: a reverse residual edge undoes flow that already cost something to send, so it carries negative cost. Breadth-first search doesn't care about edge weights at all; a plain shortest-cost search does, and negative weights rule out Dijkstra — see Pitfalls for exactly where that bites.
Same six nodes and eight directed edges as the Edmonds-Karp demo — same capacities, same max flow of 15 —
now each edge also carries a cost per unit, shown as flow/cap @cost. Press Step
or Run to repeatedly find the cheapest remaining S→T path in the residual graph
(via Bellman-Ford, which tolerates negative edges), push flow equal to its bottleneck, and repeat. A
black-bordered node and thick black edge mark the path just found; a red edge means this particular step is
using a reverse residual edge — undoing some earlier flow because that's now part of the cheapest way
forward. When no path remains, the demo reports the final max flow and its total cost.
This is the successive shortest augmenting path algorithm: at every step, among all S→T paths with spare residual capacity, take the one with the lowest total cost, not the fewest edges. The correctness argument rests on one fact worth stating plainly: the cheapest augmenting path's cost never decreases from one iteration to the next, and as long as that holds, the flow after every single augmentation is already the cheapest possible flow of that value — not just the cheapest flow the algorithm happens to finish on. Concretely, on the demo's own numbers: after iteration 4 the running total is 11 units of flow at cost 89, and that's the true minimum cost to move exactly 11 units through this network, checked independently — a from-scratch cycle-canceling implementation, seeded from a completely different (arbitrary, non-shortest-path) flow of the same 11 units at cost 106, repeatedly removed negative-cost cycles from its residual graph until none remained and landed on the identical 89. That means this algorithm doesn't just answer "cheapest way to move the maximum" — stopped early, it answers "cheapest way to move exactly this much," for every value along the way.
The reason reverse residual edges carry negative cost is direct: sending one unit forward along an edge
of cost w costs w; undoing that unit is worth −w, because it cancels a
cost already paid. The demo hits this for real at iteration 5 — by then, D→C is saturated at
its full capacity of 6, so the cheapest remaining way to reach D from C is to
partially undo that flow, traveling C→D along D→C's reverse residual edge at cost
−1. That's a genuine negative edge weight in the shortest-path subproblem, not a
hypothetical one — see Pitfalls for what breaks if it's handled with the wrong shortest-path algorithm.
Matches the demo above one for one — same capacity and cost matrices, same Bellman-Ford (Shortest Path
Faster Algorithm form: a FIFO queue instead of scanning every edge every round) rule, same residual
bookkeeping, just without the yield points the demo uses to show every intermediate
augmentation:
function minCostMaxFlow(numNodes, edges, s, t) {
// edges: [{ a, b, cap, cost }, ...] — directed, a → b, cost per unit of flow
const cap = Array.from({ length: numNodes }, () => new Array(numNodes).fill(0));
const cost = Array.from({ length: numNodes }, () => new Array(numNodes).fill(0));
edges.forEach(e => {
cap[e.a][e.b] += e.cap;
cost[e.a][e.b] = e.cost;
cost[e.b][e.a] = -e.cost; // reverse residual edge: negative cost
});
const flow = Array.from({ length: numNodes }, () => new Array(numNodes).fill(0));
let totalFlow = 0, totalCost = 0;
while (true) {
// Bellman-Ford / SPFA: shortest path by cost, tolerates negative edges
const dist = new Array(numNodes).fill(Infinity);
const parent = new Array(numNodes).fill(-1);
const inQueue = new Array(numNodes).fill(false);
dist[s] = 0;
const queue = [s];
inQueue[s] = true;
while (queue.length) {
const u = queue.shift();
inQueue[u] = false;
for (let v = 0; v < numNodes; v++) {
if (cap[u][v] - flow[u][v] > 0 && dist[u] + cost[u][v] < dist[v]) {
dist[v] = dist[u] + cost[u][v];
parent[v] = u;
if (!inQueue[v]) { queue.push(v); inQueue[v] = true; }
}
}
}
if (dist[t] === Infinity) break; // no augmenting path left — done
let bottleneck = Infinity;
for (let v = t; v !== s; v = parent[v]) {
bottleneck = Math.min(bottleneck, cap[parent[v]][v] - flow[parent[v]][v]);
}
for (let v = t; v !== s; v = parent[v]) {
flow[parent[v]][v] += bottleneck;
flow[v][parent[v]] -= bottleneck;
}
totalFlow += bottleneck;
totalCost += bottleneck * dist[t];
}
return { totalFlow, totalCost };
}Dijkstra silently returns the wrong answer once a reverse residual edge is negative — it doesn't
error out, it just finalizes a node too early. A minimal, isolated example makes the failure mode
concrete, independent of this page's own six-node graph: three nodes u, v, w, an edge
u→v of cost 0, an edge u→w of cost 1, and an edge w→v of cost −5. The
true shortest u→v is −4, via w. A standard Dijkstra — pop the lowest-distance
unvisited node, mark it visited, never revisit — pops v first at distance 0 (nothing beats it
yet) and marks it visited. When w is popped next and tries to relax v down to −4,
the visited check blocks the update. Final answer: 0, silently wrong by 4, with no error or warning anywhere
— checked by running exactly this three-node graph through a real lazy-deletion binary-heap Dijkstra:
it pops nodes in the order u (0), v (0), w (1), and reports
dist[v] = 0 instead of the true −4. Bellman-Ford has no such notion of "finalized" — every
node can be relaxed again as long as some edge still improves it — which is exactly why it tolerates
negative edges (short of a negative cycle, which a correctly-run successive-shortest-path search
never creates in the residual graph).
This naive form is pseudo-polynomial, the same honest caveat 0/1 Knapsack carries — Edmonds-Karp's BFS rule bounds its
augmentation count purely from the graph's own size (O(VE), independent of the actual capacity
values), but the cheapest-path-first rule here has no such graph-size-only bound: in an adversarial network
with many equally-cheap paths and small bottlenecks, the number of augmentations can scale with the
capacities themselves rather than staying polynomial in V and E alone. On this
page's own demo graph that's not visible — 5 augmentations on 6 nodes — but it's a real property of the
naive algorithm, not a hypothetical. Capacity scaling (process large-bottleneck paths before small ones) is
the standard fix, not implemented here.
Dijkstra can still be salvaged, just not applied directly to raw costs. After the first
Bellman-Ford call, every node has a valid shortest-path distance; using those distances as node
potentials to redefine each edge's cost as cost(u,v) + potential(u) − potential(v)
provably makes every residual edge's reduced cost non-negative from then on (a classical result, not
re-derived here), which makes every later iteration safe to run with ordinary Dijkstra instead of
Bellman-Ford — trading one O(VE) pass per augmentation for one O(E log V) pass.
This page's reference implementation always uses Bellman-Ford for simplicity and because the demo network is
small enough that the difference doesn't matter; a production implementation on a larger graph would want
the potentials version. Suurballe's Algorithm is a
worked example of exactly that version, specialized to unit-capacity edges and exactly two units of
flow: one Dijkstra call for the first path, potentials from its own distances, then a second Dijkstra
on the reduced-cost residual graph instead of a second Bellman-Ford pass.
Time: O(f · VE), where f is the number of augmenting paths
found (5 on this page's demo graph) and each one costs O(VE) for its Bellman-Ford/SPFA search
— O(V²) here specifically, since the demo represents the graph as a dense matrix rather than
adjacency lists, same as Edmonds-Karp. Unlike Edmonds-Karp, f is not bounded purely by graph
size in the worst case (see Pitfalls) — this is pseudo-polynomial, not polynomial, in its naive form.
Space: O(V²) for the capacity and cost matrices as implemented here, or
O(V + E) with adjacency lists.
See Choosing a Network Flow Algorithm for how this compares against the site's other ten Network Flow entries side by side.