Pattern Reference
Min-Cost Max-Flow
"Successive shortest augmenting path, potentials, cycle canceling, assignment problem."
Loading...
Deep Dive Tutorial
MCMF extends max-flow by adding costs: each edge (u,v) has capacity and cost per unit of flow. The residual graph has reverse edges with negative cost. Use SPFA (Bellman-Ford BFS) to find the cheapest augmenting path, then send flow along it. Repeat until no augmenting path exists. Total cost = sum of (flow × cost) on all edges. Johnson's reweighting with potentials converts negative edges to non-negative for Dijkstra.
Min-cost max-flow with SPFA
class MCMF {
constructor(n) {
this.n = n;
this.graph = Array.from({length: n}, () => []);
}
addEdge(u, v, cap, cost) {
this.graph[u].push({to: v, cap, cost, rev: this.graph[v].length});
this.graph[v].push({to: u, cap: 0, cost: -cost, rev: this.graph[u].length - 1});
}
minCostFlow(s, t, maxFlow = Infinity) {
let totalFlow = 0, totalCost = 0;
while (totalFlow < maxFlow) {
// SPFA to find shortest path in residual graph
const dist = new Array(this.n).fill(Infinity);
const inQueue = new Array(this.n).fill(false);
const prevv = new Array(this.n).fill(-1);
const preve = new Array(this.n).fill(-1);
dist[s] = 0;
const queue = [s]; inQueue[s] = true;
let qi = 0;
while (qi < queue.length) {
const u = queue[qi++]; inQueue[u] = false;
for (let i = 0; i < this.graph[u].length; i++) {
const e = this.graph[u][i];
if (e.cap > 0 && dist[u] + e.cost < dist[e.to]) {
dist[e.to] = dist[u] + e.cost;
prevv[e.to] = u; preve[e.to] = i;
if (!inQueue[e.to]) { inQueue[e.to] = true; queue.push(e.to); }
}
}
}
if (dist[t] === Infinity) break;
// Find bottleneck flow along augmenting path
let d = maxFlow - totalFlow;
for (let v = t; v !== s; v = prevv[v])
d = Math.min(d, this.graph[prevv[v]][preve[v]].cap);
// Augment
for (let v = t; v !== s; v = prevv[v]) {
const e = this.graph[prevv[v]][preve[v]];
e.cap -= d;
this.graph[v][e.rev].cap += d;
}
totalFlow += d; totalCost += d * dist[t];
}
return { flow: totalFlow, cost: totalCost };
}
}Worked Problems
banknote
MCMF applications:
- Transportation (ship goods from factories to stores minimizing cost)
- Assignment problem: assign n workers to n jobs minimizing total cost
- Project scheduling with resource costs
Complexity: O(V × E × max_flow) with SPFA. For dense graphs, use Johnson's potentials + Dijkstra: O(E log V × max_flow).
Relationship to min-cost bipartite matching: MCMF on a bipartite graph where each left/right node has capacity 1 = minimum cost perfect matching. Hungarian algorithm is O(n³) for n×n assignment problem.
Successive shortest paths: Each augmentation sends flow along the cheapest augmenting path. The key insight: as long as we always take the cheapest path, total cost remains optimal.
- Transportation (ship goods from factories to stores minimizing cost)
- Assignment problem: assign n workers to n jobs minimizing total cost
- Project scheduling with resource costs
Complexity: O(V × E × max_flow) with SPFA. For dense graphs, use Johnson's potentials + Dijkstra: O(E log V × max_flow).
Relationship to min-cost bipartite matching: MCMF on a bipartite graph where each left/right node has capacity 1 = minimum cost perfect matching. Hungarian algorithm is O(n³) for n×n assignment problem.
Successive shortest paths: Each augmentation sends flow along the cheapest augmenting path. The key insight: as long as we always take the cheapest path, total cost remains optimal.