---
title: "Max Flow: Ford–Fulkerson, Dinic, Push–Relabel"
summary: Three augmenting strategies, why each terminates, Dinic's O(V^2 E) proof, and how to read the min cut out of the residual graph.
difficulty: hard
tags: [flow, graphs, optimisation]
time: V^2 E (Dinic)
space: V + E
prereq: [flow/cuts, shortest/dijkstra]
see: [flow/mincut-models, matching/bipartite]
demo: maxflow
---

:::definition label="Augmenting path method"
While a path $s \leadsto t$ exists in the residual graph $G_f$, take one and push the bottleneck capacity along it. The flow stays feasible, strictly increases, and stops exactly when no such path exists.
:::

:::theorem title="Termination and correctness"
If capacities are integral, the algorithm terminates with a maximum flow, and $|f| = c(S,\bar S)$ where $S$ is the set of vertices reachable from $s$ in the final $G_f$.
:::

:::proof
Each augmentation increases $|f|$ by at least 1 (integral bottlenecks), and $|f| \le \sum_{v} c(s,v)$ bounds it above — so it terminates. At termination $S$ is well defined and $t \notin S$. Every edge out of $S$ is *saturated* (else its head would be reachable), and every edge into $S$ carries *zero* flow (else the reverse residual edge would make its tail reachable). Hence
$$c(S,\bar S) = \sum_{u\in S,v\notin S} c(u,v) = \sum f(u,v) = |f|,$$
and weak duality (@flow/cuts) then makes $f$ maximum and $(S,\bar S)$ minimum. ∎
:::

## Three ways to pick the path
| algorithm | choice | bound | practical |
|---|---|---|---|
| Ford–Fulkerson (DFS) | arbitrary | $O(|f| \cdot E)$ — unbounded with irrational capacities | never use; can be exponentially slow with "bad" paths |
| Edmonds–Karp | shortest (BFS) | $O(V E^2)$ | reliable, $V E^2$ up to a few $10^7$ |
| **Dinic** | blocking flow in the level graph | $O(V^2 E)$, $O(E\sqrt V)$ unit-capacity, $O(V^{2/3}E)$ unit-network | the default; usually 10–100× the bound |
| Push–relabel (FIFO/highest) | local saturate + relabel | $O(V^2\sqrt E)$ with gap+global relabel heuristics, $O(V^3)$ plain | fastest on dense graphs and on huge sparse ones with good heuristics |

```cpp dinic.cpp
struct Edge { int to, rev, cap; };
vector<vector<Edge>> g(n);
void add(int u, int v, int cap) {           // residual pair: forward cap, backward 0
    g[u].push_back({v, (int)g[v].size(), cap});
    g[v].push_back({u, (int)g[u].size() - 1, 0});
}
int lvl[n], it[n];
bool bfs() {
    fill(lvl, lvl + n, -1); queue<int> q{ }; lvl[s] = 0; q.push(s);
    while (q.size()) {
        int v = q.front(); q.pop();
        for (auto &e : g[v]) if (e.cap && lvl[e.to] < 0) { lvl[e.to] = lvl[v] + 1; q.push(e.to); }
    }
    return lvl[t] >= 0;
}
int dfs(int v, int pushed) {                 // blocking flow, one DFS "cursor" per vertex
    if (v == t) return pushed;
    for (int &cid = it[v]; cid < (int)g[v].size(); cid++) {
        Edge &e = g[v][cid];
        if (e.cap && lvl[e.to] == lvl[v] + 1) {
            int tr = dfs(e.to, min(pushed, e.cap));
            if (!tr) continue;
            e.cap -= tr; g[e.to][e.rev].cap += tr;
            return tr;
        }
    }
    return 0;
}
long long flow = 0;
while (bfs()) {
    fill(it, it + n, 0);
    while (int pushed = dfs(s, INF)) flow += pushed;
}
```

:::theorem title="Dinic: O(V^2 E)"
Each phase (one BFS + one blocking flow) costs $O(VE)$, and there are at most $V-1$ phases.
:::

:::proof
The blocking flow computation is $O(VE)$: every DFS either saturates an edge (at most $E$ saturations) or advances a cursor `it[v]` permanently (at most $V+E$ cursor steps per unit... formally, the total number of `dfs` calls that return 0 is bounded by the number of cursor advances, $O(VE)$ including the path lengths). For the phase count: after a phase, the shortest augmenting-path length strictly increases (a standard argument: any new residual $s$–$t$ path must use a *backward* edge of the blocking flow, which skips at least one level, so its length grows), and lengths are at most $V-1$. ∎
:::

:::props title="How the min cut is read off"
- run to completion, then BFS from $s$ in the residual graph → $S$; the cut edges are the original edges from $S$ to $\bar S$,
- **"which vertices can be on the source side of *some* min cut?"** — the family of min cuts forms a lattice; contract strongly-connected components of the final residual graph, and the min cuts correspond to closed sets of the condensation that contain $\operatorname{scc}(s)$ and exclude $\operatorname{scc}(t)$: a vertex is in *all* min cuts' source sides iff $\operatorname{scc}(s)$ reaches it, in *none* iff it reaches $\operatorname{scc}(t)$,
- **minimum number of edges to delete to separate $s,t$** = max flow with unit capacities (Menger again, @foundations/connectivity), and the deletion set is the cut's forward edges.
:::

:::demo id="maxflow" caption="Dinic's level graph: grey edges are unusable (wrong level), green carries the blocking flow. Watch the phase count on the pathological graph — the level of t rises by one each phase, which is the V-1 bound being tight."
:::

:::note title="Push–relabel, in one paragraph"
Maintain a *pre-flow* (excess allowed at internal vertices) and heights $h$ with $h(s)=n$, $h(t)=0$, and the validity condition $h(u) \le h(v)+1$ for every residual edge. **Push** along admissible edges ($h(u) = h(v)+1$) as much as capacity allows; **relabel** a vertex with excess by setting $h(u) = 1 + \min h(v)$ over residual out-edges. Termination: no excess outside $s,t$ ⇒ a valid flow; maximality: $h(u) \ge n$ marks "u cannot reach $t$", and $\{u : h(u) \ge n\}$ is a min cut's source side. With **highest-label selection + gap relabelling + periodic global relabel** (BFS backwards from $t$ in the residual graph), it is the fastest known in practice for dense/large networks.
:::

:::warning title="Capacity size, not graph size, is what bites"
- Use `long long` for capacities and the answer; `int` overflows at $2\times10^9$, and summing 1000 edges of $10^9$ out of $s$ is a standard WA,
- **parallel edges**: merge them or (easier) let the adjacency list hold several `Edge`s — Dinic handles it, but `cap[u][v] = c` in a matrix *overwrites*; CSES Download Speed tests exactly this,
- **anti-parallel** edges ($u \to v$ and $v \to u$ both exist): you cannot use the "reverse edge index" trick naively — store `rev` per edge as above and it works, but a matrix implementation double-counts,
- recursion depth in `dfs` is $O(V)$: fine at $2\times10^5$ with care, add `it`-based iteration or an explicit stack if $V = 10^6$.
:::

:::problems
- [[CSES 1694]] Download Speed | https://cses.fi/problemset/task/1694 | core | parallel edges and capacity types
- [[CSES 1695]] Police Chase | https://cses.fi/problemset/task/1695 | core | unit capacities, edge-disjoint paths
- [[CSES 1711]] Distinct Routes | https://cses.fi/problemset/task/1711 | hard | recover $k$ edge-disjoint *paths* from the flow decomposition
- [[CSES 2130]] Distinct Routes II | https://cses.fi/problemset/task/2130 | hard | vertex capacities: split every vertex
:::