AntInLoop

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 4 along 0→1→3→5, 6 along 0→1→4→5, 4 along 0→2→4→5 (total pushed = 14).
  • Phase 2 (BFS reaches T via 0→2→4→3→5):
  • Pushes 5 along 0→2→4→3→5 (total = 19).
  • Phase 3: T unreachable in residual graph → Max Flow = 19!

---

Complexity & Key Insights

  • Current-Arc Optimization (ptr[u]): Without ptr[u], DFS can re-visit dead-end edges repeatedly inside one phase, degrading worst-case complexity. With ptr[u], each blocking-flow phase takes $O(V E)$, and since level[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 S over edges with cap > 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 → i with capacity p[i] for every profitable project (p[i] > 0).
  • Add edge i → T with capacity -p[i] for every cost project (p[i] < 0).
  • Add edge u → v with capacity INF for every dependency (u requires v).

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