Pattern Guide
Min-Cost Max-Flow
"Find max flow with minimum total cost. SPFA/Bellman-Ford on residual graph."
Min-cost max-flow (MCMF) finds the maximum flow from source to sink while minimizing the total cost of edges used. Each edge has both capacity and cost per unit of flow. Algorithm: repeat SPFA (Bellman-Ford BFS) to find shortest (min-cost) augmenting path in the residual graph, augment along it. Applications: transportation, assignment problems, and project scheduling with costs.
Problems you can solve with this pattern
3 problems · click any to start solving
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 };
}
}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.
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 };
}
}- 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.