Pattern Guide
Network Flow
"Max flow = min cut. Dinic's runs in O(V²E). Models matching, assignment, feasibility."
Network flow finds the maximum amount of "flow" from source to sink respecting edge capacities. The max-flow min-cut theorem: max flow equals min cut capacity. Algorithms: Ford-Fulkerson (DFS, slow), Edmonds-Karp (BFS augmenting paths, O(VE²)), Dinic's (level graph + blocking flow, O(V²E), O(E√V) for unit graphs). Applications: bipartite matching, assignment problems, project selection.
Problems you can solve with this pattern
4 problems · click any to start solving
class MaxFlow {
constructor(n) {
this.n = n;
this.graph = Array.from({length: n}, () => []);
}
addEdge(u, v, cap) {
this.graph[u].push({to: v, cap, rev: this.graph[v].length});
this.graph[v].push({to: u, cap: 0, rev: this.graph[u].length - 1});
}
bfs(s, t, level) {
level.fill(-1); level[s] = 0;
const queue = [s]; let i = 0;
while (i < queue.length) {
const u = queue[i++];
for (const e of this.graph[u]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[u] + 1;
queue.push(e.to);
}
}
}
return level[t] >= 0;
}
dfs(u, t, f, level, iter) {
if (u === t) return f;
for (; iter[u] < this.graph[u].length; iter[u]++) {
const e = this.graph[u][iter[u]];
if (e.cap > 0 && level[e.to] === level[u] + 1) {
const d = this.dfs(e.to, t, Math.min(f, e.cap), level, iter);
if (d > 0) {
e.cap -= d;
this.graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
maxflow(s, t) {
const level = new Array(this.n), iter = new Array(this.n);
let flow = 0;
while (this.bfs(s, t, level)) {
iter.fill(0);
let f;
while ((f = this.dfs(s, t, Infinity, level, iter)) > 0) flow += f;
}
return flow;
}
}Network flow models problems where you want to route maximum "stuff" (data, goods, people) through a network with capacities. The key insight: max-flow equals min-cut — the bottleneck is always some set of edges whose total capacity limits all paths from source to sink. Dinic's algorithm uses BFS to build a "level graph" then finds blocking flows layer by layer — much faster than naive augmenting paths.
class MaxFlow {
constructor(n) {
this.n = n;
this.graph = Array.from({length: n}, () => []);
}
addEdge(u, v, cap) {
this.graph[u].push({to: v, cap, rev: this.graph[v].length});
this.graph[v].push({to: u, cap: 0, rev: this.graph[u].length - 1});
}
bfs(s, t, level) {
level.fill(-1); level[s] = 0;
const queue = [s]; let i = 0;
while (i < queue.length) {
const u = queue[i++];
for (const e of this.graph[u]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[u] + 1;
queue.push(e.to);
}
}
}
return level[t] >= 0;
}
dfs(u, t, f, level, iter) {
if (u === t) return f;
for (; iter[u] < this.graph[u].length; iter[u]++) {
const e = this.graph[u][iter[u]];
if (e.cap > 0 && level[e.to] === level[u] + 1) {
const d = this.dfs(e.to, t, Math.min(f, e.cap), level, iter);
if (d > 0) {
e.cap -= d;
this.graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
maxflow(s, t) {
const level = new Array(this.n), iter = new Array(this.n);
let flow = 0;
while (this.bfs(s, t, level)) {
iter.fill(0);
let f;
while ((f = this.dfs(s, t, Infinity, level, iter)) > 0) flow += f;
}
return flow;
}
}Algorithm selection:
- Edmonds-Karp (BFS augmenting): O(VE²) — simple to implement
- Dinic's: O(V²E), O(E√V) for unit capacity — fast in practice
- For bipartite matching: any max-flow works; O(E√V) with Hopcroft-Karp
Modeling tricks:
- Node capacity: split node v into v_in → v_out with edge capacity = node limit
- Bidirectional edge: add both directions with their capacities
- Lower bounds on flow: shift using supply/demand at nodes
Applications: bipartite matching (König's: max matching = total - max flow complement), project selection (each project profits/costs modeled as source/sink edges), circulation with demands.