Push as much flow as possible from source 0 to sink 5 with Dinic's algorithm. A phase starts with a BFS that labels every vertex with its distance from 0 through edges that still have room. The number on each vertex is that level. Only edges that go up exactly one level are used for the phase, and paths are pushed through them until none is left, a blocking flow. Then the levels are rebuilt. Each phase makes the shortest path strictly longer, so there are at most V phases.
The code
Maximum Flow, in Python
def max_flow(cap, s, t, bfs):
flow = [[0] * n for _ in range(n)] # flow[v][u] == -flow[u][v]
total = 0
while True:
parent = bfs_path(s, t) if bfs else dfs_path(s, t) # residual(u, v) > 0 edges only
if parent[t] < 0: # t unreachable: no augmenting path
break
bottleneck = float("inf")
v = t
while v != s:
u = parent[v]
bottleneck = min(bottleneck, residual(u, v))
v = u
v = t
while v != s:
u = parent[v]
flow[u][v] += bottleneck
flow[v][u] -= bottleneck
v = u
total += bottleneck
return total
def residual(u, v):
return cap[u][v] - flow[u][v] # undoing flow on v->u counts as room on u->v
def min_cut(): # after max_flow
reachable = bfs_reachable(s) # S side: still reachable in the residual graph
return [(u, v) for u, v in edges if u in reachable and v not in reachable] # all saturated, summing to the flow
def bipartite_matching(left, right, pairs):
# s -> every left vertex, left -> right along the pairs, every right vertex -> t, all capacity 1
return max_flow(unit_network(left, right, pairs), s, t, bfs=True) # each path is an alternating path
def dinic(s, t):
total = 0
while True:
level = bfs_levels(s) # residual edges only, distance from s
if level[t] < 0: # t unreachable: done
return total
while True: # a blocking flow in this level graph
path = dfs_path(s, t, lambda u, v: level[v] == level[u] + 1 and residual(u, v) > 0)
if path is None: # no path left at these levels: next phase
break
amount = min(residual(u, v) for u, v in zip(path, path[1:]))
push(path, amount)
total += amount
# at most V phases: O(V^2 E)
Maximum Flow, in JavaScript
function maxFlow(cap, s, t, bfs) {
const flow = Array.from({ length: n }, () => new Array(n).fill(0)); // flow[v][u] == -flow[u][v]
let total = 0;
while (true) {
const parent = bfs ? bfsPath(s, t) : dfsPath(s, t); // residual(u, v) > 0 edges only
if (parent[t] < 0) break; // t unreachable: no augmenting path
let bottleneck = Infinity;
let v = t;
while (v !== s) {
const u = parent[v];
bottleneck = Math.min(bottleneck, residual(u, v));
v = u;
}
v = t;
while (v !== s) {
const u = parent[v];
flow[u][v] += bottleneck;
flow[v][u] -= bottleneck;
v = u;
}
total += bottleneck;
}
return total;
}
function residual(u, v) {
return cap[u][v] - flow[u][v]; // undoing flow on v->u counts as room on u->v
}
function minCut() { // after maxFlow
const reachable = bfsReachable(s); // S side: still reachable in the residual graph
return edges.filter(([u, v]) => reachable.has(u) && !reachable.has(v)); // all saturated, summing to the flow
}
function bipartiteMatching(left, right, pairs) {
// s -> every left vertex, left -> right along the pairs, every right vertex -> t, all capacity 1
return maxFlow(unitNetwork(left, right, pairs), s, t, true); // each path is an alternating path
}
function dinic(s, t) {
let total = 0;
while (true) {
const level = bfsLevels(s); // residual edges only, distance from s
if (level[t] < 0) return total; // t unreachable: done
while (true) { // a blocking flow in this level graph
const path = dfsPath(s, t, (u, v) => level[v] === level[u] + 1 && residual(u, v) > 0);
if (path == null) break; // no path left at these levels: next phase
const amount = Math.min(...path.slice(0, -1).map((u, i) => residual(u, path[i + 1])));
push(path, amount);
total += amount;
}
}
} // at most V phases: O(V^2 E)
Maximum Flow, in Kotlin
fun maxFlow(cap: Array<IntArray>, s: Int, t: Int, bfs: Boolean): Int {
val flow = Array(n) { IntArray(n) } // flow[v][u] == -flow[u][v]
var total = 0
while (true) {
val parent = if (bfs) bfsPath(s, t) else dfsPath(s, t) // residual(u, v) > 0 edges only
if (parent[t] < 0) break // t unreachable: no augmenting path
var bottleneck = Int.MAX_VALUE
var v = t
while (v != s) { val u = parent[v]; bottleneck = min(bottleneck, residual(u, v)); v = u }
v = t
while (v != s) { val u = parent[v]; flow[u][v] += bottleneck; flow[v][u] -= bottleneck; v = u }
total += bottleneck
}
return total
}
fun residual(u: Int, v: Int) = cap[u][v] - flow[u][v] // undoing flow on v->u counts as room on u->v
fun minCut(): List<Pair<Int, Int>> { // after maxFlow
val reachable = bfsReachable(s) // S side: still reachable in the residual graph
return edges.filter { (u, v) -> u in reachable && v !in reachable } // all saturated, summing to the flow
}
fun bipartiteMatching(left: Int, right: Int, pairs: List<Pair<Int, Int>>): Int {
// s -> every left vertex, left -> right along the pairs, every right vertex -> t, all capacity 1
return maxFlow(unitNetwork(left, right, pairs), s, t, bfs = true) // each path is an alternating path
}
fun dinic(s: Int, t: Int): Int {
var total = 0
while (true) {
val level = bfsLevels(s) // residual edges only, distance from s
if (level[t] < 0) return total // t unreachable: done
while (true) { // a blocking flow in this level graph
val path = dfsPath(s, t) { u, v -> level[v] == level[u] + 1 && residual(u, v) > 0 }
?: break // no path left at these levels: next phase
val amount = path.zipWithNext().minOf { (u, v) -> residual(u, v) }
push(path, amount); total += amount
}
}
} // at most V phases: O(V^2 E)