Dinic's Algorithm (Maximum Flow)
Dinic's Algorithm computes the maximum flow in a flow network by repeatedly building a BFS level graph and pushing blocking flows via DFS with current-arc optimization.
Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code
Dinic's Algorithm (Maximum Flow)
Dinic's Algorithm finds the maximum flow from a source $S$ to a sink $T$ in a directed capacitated network (and by the Max-Flow Min-Cut Theorem, simultaneously finds the minimum $S\text{–}T$ cut). By repeatedly building a shortest-path level graph via BFS and saturating it with a blocking flow via DFS, Dinic's outperforms Edmonds–Karp ($O(V E^2)$) and runs in $O(E \sqrt{V})$ on unit-capacity / bipartite matching networks!
At a Glance
| Property | Value |
| :--- | :--- |
| General Time Complexity | $O(V^2 E)$ (much faster in practice) |
| Unit-Capacity / Bipartite Matching | $O(E \sqrt{V})$ |
| Auxiliary Space | $O(V + E)$ |
| Finds Min-Cut Too? | Yes (reachable vertices from $S$ in the final residual graph) |
| Best Used When | Maximum flow, minimum cut, maximum bipartite matching, edge-disjoint paths |
---
How It Works
Each directed edge u → v with capacity cap is paired with a reverse residual edge v → u of initial capacity 0.
1. BFS Level Graph: Starting from S, assign level[v] = level[u] + 1 along edges with remaining capacity cap > 0. If T is unreachable, stop—the current flow is maximum!
2. DFS Blocking Flow (with Current-Arc Pointer ptr[u]): Repeatedly push flow from S to T along edges satisfying level[v] == level[u] + 1 and cap > 0, updating ptr[u] so dead-end edges are never re-scanned within the same BFS phase.
3. Repeat until BFS can no longer reach T.
procedure dinic(S, T):
totalFlow = 0
while bfsBuildLevelGraph(S, T):
reset ptr[0..V-1] = 0
while (pushed = dfsPush(S, T, INF)) > 0:
totalFlow += pushed
return totalFlow
Step-by-Step Trace
Network 0→1 (10), 0→2 (10), 1→2 (2), 1→3 (4), 1→4 (8), 2→4 (9), 4→3 (6), 3→5 (10), 4→5 (10), S = 0, T = 5:
- Phase 1 (BFS levels
0:0, 1:1, 2:1, 3:2, 4:2, 5:3): - Pushes
4along0→1→3→5,6along0→1→4→5,4along0→2→4→5(total pushed =14). - Phase 2 (BFS reaches
Tvia0→2→4→3→5): - Pushes
5along0→2→4→3→5(total =19). - Phase 3:
Tunreachable in residual graph → Max Flow =19!
---
Complexity & Key Insights
- Current-Arc Optimization (
ptr[u]): Withoutptr[u], DFS can re-visit dead-end edges repeatedly inside one phase, degrading worst-case complexity. Withptr[u], each blocking-flow phase takes $O(V E)$, and sincelevel[T]strictly increases each phase (at most $V - 1$ phases), total time is $O(V^2 E)$. - Max-Flow = Min-Cut: Once Dinic terminates, run one final BFS/DFS from
Sover edges withcap > 0. Every original edge going from a reachable vertex to an unreachable vertex belongs to the minimum $S\text{–}T$ cut!
---
Practice Problems
Easy
1. Standard Maximum Flow
Compute the maximum flow from S to T in a directed weighted network using Dinic's Algorithm.
Approach: Reusable Dinic struct with addEdge, bfs, and dfs with current-arc pointer ptr. Time: $O(V^2 E)$. Space: $O(V + E)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <limits>
#include <queue>
#include <vector>
struct Dinic {
struct Edge { int to, rev; long long cap; };
int n;
std::vector<std::vector<Edge>> adj;
std::vector<int> level, ptr;
explicit Dinic(int n) : n(n), adj(n), level(n), ptr(n) {}
void addEdge(int u, int v, long long cap) {
adj[u].push_back({v, static_cast<int>(adj[v].size()), cap});
adj[v].push_back({u, static_cast<int>(adj[u].size()) - 1, 0});
}
bool bfs(int s, int t) {
std::fill(level.begin(), level.end(), -1);
std::queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (const auto& e : adj[u]) {
if (e.cap > 0 && level[e.to] == -1) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
return level[t] != -1;
}
long long dfs(int u, int t, long long pushed) {
if (pushed == 0 || u == t) return pushed;
for (int& cid = ptr[u]; cid < static_cast<int>(adj[u].size()); ++cid) {
Edge& e = adj[u][cid];
if (e.cap > 0 && level[e.to] == level[u] + 1) {
long long tr = dfs(e.to, t, std::min(pushed, e.cap));
if (tr > 0) {
e.cap -= tr;
adj[e.to][e.rev].cap += tr;
return tr;
}
}
}
return 0;
}
long long maxFlow(int s, int t) {
long long flow = 0;
const long long INF = std::numeric_limits<long long>::max() / 4;
while (bfs(s, t)) {
std::fill(ptr.begin(), ptr.end(), 0);
while (long long pushed = dfs(s, t, INF)) flow += pushed;
}
return flow;
}
};
int main() {
Dinic d(6);
d.addEdge(0, 1, 10); d.addEdge(0, 2, 10); d.addEdge(1, 2, 2);
d.addEdge(1, 3, 4); d.addEdge(1, 4, 8); d.addEdge(2, 4, 9);
d.addEdge(4, 3, 6); d.addEdge(3, 5, 10); d.addEdge(4, 5, 10);
std::cout << "Max flow: " << d.maxFlow(0, 5) << "\n";
return 0;
}
</details>
2. Maximum Bipartite Matching in $O(E \sqrt{V})$
Given $L$ applicants, $R$ jobs, and allowed (applicant, job) pairs, find the maximum number of jobs that can be assigned.
Approach: Add a super-source S with capacity-1 edges to all left nodes, capacity-1 edges for allowed pairs, and capacity-1 edges from all right nodes to a super-sink T. Run Dinic's! Time: $O(E \sqrt{V})$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
struct Dinic {
struct Edge { int to, rev, cap; };
std::vector<std::vector<Edge>> adj;
std::vector<int> level, ptr;
explicit Dinic(int n) : adj(n), level(n), ptr(n) {}
void addEdge(int u, int v, int cap) {
adj[u].push_back({v, static_cast<int>(adj[v].size()), cap});
adj[v].push_back({u, static_cast<int>(adj[u].size()) - 1, 0});
}
bool bfs(int s, int t) {
std::fill(level.begin(), level.end(), -1);
std::queue<int> q; level[s] = 0; q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (const auto& e : adj[u])
if (e.cap > 0 && level[e.to] == -1) { level[e.to] = level[u] + 1; q.push(e.to); }
}
return level[t] != -1;
}
int dfs(int u, int t, int pushed) {
if (pushed == 0 || u == t) return pushed;
for (int& cid = ptr[u]; cid < static_cast<int>(adj[u].size()); ++cid) {
auto& e = adj[u][cid];
if (e.cap > 0 && level[e.to] == level[u] + 1) {
int tr = dfs(e.to, t, std::min(pushed, e.cap));
if (tr > 0) { e.cap -= tr; adj[e.to][e.rev].cap += tr; return tr; }
}
}
return 0;
}
int maxFlow(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
std::fill(ptr.begin(), ptr.end(), 0);
while (int pushed = dfs(s, t, 1e9)) flow += pushed;
}
return flow;
}
};
int main() {
int L = 3, R = 3, S = 0, T = L + R + 1;
Dinic d(T + 1);
for (int i = 1; i <= L; ++i) d.addEdge(S, i, 1);
for (int j = 1; j <= R; ++j) d.addEdge(L + j, T, 1);
std::vector<std::pair<int, int>> pairs = {{1, 1}, {1, 2}, {2, 2}, {3, 2}, {3, 3}};
for (const auto& [a, j] : pairs) d.addEdge(a, L + j, 1);
std::cout << "Max matching: " << d.maxFlow(S, T) << "\n";
return 0;
}
</details>
---
Intermediate
3. Minimum $S\text{–}T$ Cut Edges
Find both the minimum cut capacity and the actual edges crossing the minimum $S\text{–}T$ cut.
Approach: Run Dinic's to compute max flow. Afterward, level[u] != -1 from the final failed BFS marks exactly the set of vertices reachable from S in the residual graph! Every original edge (u, v) with level[u] != -1 && level[v] == -1 belongs to the minimum cut. Time: $O(V^2 E)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
struct Dinic {
struct Edge { int to, rev, cap; bool orig; };
std::vector<std::vector<Edge>> adj;
std::vector<int> level, ptr;
explicit Dinic(int n) : adj(n), level(n), ptr(n) {}
void addEdge(int u, int v, int cap) {
adj[u].push_back({v, static_cast<int>(adj[v].size()), cap, true});
adj[v].push_back({u, static_cast<int>(adj[u].size()) - 1, 0, false});
}
bool bfs(int s, int t) {
std::fill(level.begin(), level.end(), -1);
std::queue<int> q; level[s] = 0; q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (const auto& e : adj[u])
if (e.cap > 0 && level[e.to] == -1) { level[e.to] = level[u] + 1; q.push(e.to); }
}
return level[t] != -1;
}
int dfs(int u, int t, int pushed) {
if (pushed == 0 || u == t) return pushed;
for (int& cid = ptr[u]; cid < static_cast<int>(adj[u].size()); ++cid) {
auto& e = adj[u][cid];
if (e.cap > 0 && level[e.to] == level[u] + 1) {
int tr = dfs(e.to, t, std::min(pushed, e.cap));
if (tr > 0) { e.cap -= tr; adj[e.to][e.rev].cap += tr; return tr; }
}
}
return 0;
}
int maxFlow(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
std::fill(ptr.begin(), ptr.end(), 0);
while (int pushed = dfs(s, t, 1e9)) flow += pushed;
}
return flow;
}
};
int main() {
Dinic d(4);
d.addEdge(0, 1, 3); d.addEdge(0, 2, 2); d.addEdge(1, 2, 5);
d.addEdge(1, 3, 2); d.addEdge(2, 3, 3);
int cutCap = d.maxFlow(0, 3);
std::cout << "Min cut: " << cutCap << " | edges:";
for (int u = 0; u < 4; ++u) {
if (d.level[u] == -1) continue;
for (const auto& e : d.adj[u]) {
if (e.orig && d.level[e.to] == -1) std::cout << " " << u << "->" << e.to;
}
}
std::cout << "\n";
return 0;
}
</details>
4. Maximum Edge-Disjoint Paths from $S$ to $T$
Find the maximum number of paths from S to T in a directed graph that share no edges.
Approach: Give every directed edge capacity 1 and run Dinic's max flow! Each unit of flow corresponds to one edge-disjoint path. Time: $O(E \sqrt{V})$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
struct Dinic {
struct Edge { int to, rev, cap; };
std::vector<std::vector<Edge>> adj;
std::vector<int> level, ptr;
explicit Dinic(int n) : adj(n), level(n), ptr(n) {}
void addEdge(int u, int v, int cap) {
adj[u].push_back({v, static_cast<int>(adj[v].size()), cap});
adj[v].push_back({u, static_cast<int>(adj[u].size()) - 1, 0});
}
bool bfs(int s, int t) {
std::fill(level.begin(), level.end(), -1);
std::queue<int> q; level[s] = 0; q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (const auto& e : adj[u])
if (e.cap > 0 && level[e.to] == -1) { level[e.to] = level[u] + 1; q.push(e.to); }
}
return level[t] != -1;
}
int dfs(int u, int t, int pushed) {
if (pushed == 0 || u == t) return pushed;
for (int& cid = ptr[u]; cid < static_cast<int>(adj[u].size()); ++cid) {
auto& e = adj[u][cid];
if (e.cap > 0 && level[e.to] == level[u] + 1) {
int tr = dfs(e.to, t, std::min(pushed, e.cap));
if (tr > 0) { e.cap -= tr; adj[e.to][e.rev].cap += tr; return tr; }
}
}
return 0;
}
int maxFlow(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
std::fill(ptr.begin(), ptr.end(), 0);
while (int pushed = dfs(s, t, 1e9)) flow += pushed;
}
return flow;
}
};
int main() {
Dinic d(6);
d.addEdge(0, 1, 1); d.addEdge(0, 2, 1); d.addEdge(1, 3, 1);
d.addEdge(2, 3, 1); d.addEdge(2, 4, 1); d.addEdge(3, 5, 1); d.addEdge(4, 5, 1);
std::cout << "Edge-disjoint paths: " << d.maxFlow(0, 5) << "\n";
return 0;
}
</details>
---
Hard
5. Project Selection (Maximum-Weight Closure via Min-Cut)
You have $n$ projects with profit p[i] (positive = revenue, negative = cost) and dependencies u requires v. Pick a valid subset of projects maximizing total profit.
Approach: Classic Project Selection reduction to Min-Cut:
- Add edge
S → iwith capacityp[i]for every profitable project (p[i] > 0). - Add edge
i → Twith capacity-p[i]for every cost project (p[i] < 0). - Add edge
u → vwith capacityINFfor every dependency (urequiresv).
Then maxProfit = sum(positive p[i]) - minCut(S, T)! Time: $O(V^2 E)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
struct Dinic {
struct Edge { int to, rev; long long cap; };
std::vector<std::vector<Edge>> adj;
std::vector<int> level, ptr;
explicit Dinic(int n) : adj(n), level(n), ptr(n) {}
void addEdge(int u, int v, long long cap) {
adj[u].push_back({v, static_cast<int>(adj[v].size()), cap});
adj[v].push_back({u, static_cast<int>(adj[u].size()) - 1, 0});
}
bool bfs(int s, int t) {
std::fill(level.begin(), level.end(), -1);
std::queue<int> q; level[s] = 0; q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (const auto& e : adj[u])
if (e.cap > 0 && level[e.to] == -1) { level[e.to] = level[u] + 1; q.push(e.to); }
}
return level[t] != -1;
}
long long dfs(int u, int t, long long pushed) {
if (pushed == 0 || u == t) return pushed;
for (int& cid = ptr[u]; cid < static_cast<int>(adj[u].size()); ++cid) {
auto& e = adj[u][cid];
if (e.cap > 0 && level[e.to] == level[u] + 1) {
long long tr = dfs(e.to, t, std::min(pushed, e.cap));
if (tr > 0) { e.cap -= tr; adj[e.to][e.rev].cap += tr; return tr; }
}
}
return 0;
}
long long maxFlow(int s, int t) {
long long flow = 0;
while (bfs(s, t)) {
std::fill(ptr.begin(), ptr.end(), 0);
while (long long pushed = dfs(s, t, 1e15)) flow += pushed;
}
return flow;
}
};
int main() {
// Projects 0..3 with profits {+10, +6, -7, -5}; 0 requires 2, 1 requires 2 and 3
std::vector<long long> profit = {10, 6, -7, -5};
std::vector<std::pair<int, int>> deps = {{0, 2}, {1, 2}, {1, 3}};
int n = static_cast<int>(profit.size()), S = n, T = n + 1;
Dinic d(n + 2);
long long totalPos = 0;
for (int i = 0; i < n; ++i) {
if (profit[i] > 0) { totalPos += profit[i]; d.addEdge(S, i, profit[i]); }
else d.addEdge(i, T, -profit[i]);
}
for (const auto& [u, v] : deps) d.addEdge(u, v, 1e15);
std::cout << "Max profit: " << (totalPos - d.maxFlow(S, T)) << "\n"; // 10+6-7-5 = 4
return 0;
}
</details>
---
Related Algorithms
- Breadth-First Search (BFS) — builds Dinic's level graph in each phase.
- Depth-First Search (DFS) — pushes blocking flows along shortest augmenting paths.