Dinic’s Algorithm

Dinic’s Algorithm is an efficient algorithm for finding the Maximum Flow in a flow network. It runs in $O(V^2 E)$ time for general graphs and $O(E \sqrt{V})$ for unit capacity graphs.

Flow Network

• Source $s$: The node where flow originates.
• Sink $t$: The node where flow is collected.
• Capacity $c(u, v)$: The maximum flow allowed on edge $(u, v)$.
• Flow $f(u, v)$: The current flow on edge $(u, v)$.

Algorithm Overview

1. BFS builds a level graph (distance from source).
2. DFS finds blocking flows in the level graph.
3. Repeat until no more augmenting paths exist.

Implementation

struct Dinic {
    struct Edge {
        int to, rev;
        long long cap;
    };
    int n;
    vector<vector<Edge>> graph;
    vector<int> level, iter;
    Dinic(int n) : n(n), graph(n), level(n), iter(n) {}
    void addEdge(int from, int to, long long cap) {
        graph[from].push_back({to, (int)graph[to].size(), cap});
        graph[to].push_back({from, (int)graph[from].size() - 1, 0});
    }
    void addBidirectionalEdge(int from, int to, long long cap) {
        graph[from].push_back({to, (int)graph[to].size(), cap});
        graph[to].push_back({from, (int)graph[from].size() - 1, cap});
    }
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : graph[u]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }
    long long dfs(int u, int t, long long f) {
        if (u == t) return f;
        for (int& i = iter[u]; i < graph[u].size(); i++) {
            Edge& e = graph[u][i];
            if (e.cap > 0 && level[u] < level[e.to]) {
                long long d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    graph[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    long long maxFlow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            fill(iter.begin(), iter.end(), 0);
            long long f;
            while ((f = dfs(s, t, LLONG_MAX)) > 0) {
                flow += f;
            }
        }
        return flow;
    }
};

Example Usage

int main() {
    int n, m;
    cin >> n >> m;
    Dinic dinic(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        dinic.addEdge(u, v, c);
    }
    int source = 0, sink = n - 1;
    cout << dinic.maxFlow(source, sink) << endl;
    return 0;
}

Key Theorems

Max-Flow Min-Cut Theorem

$\text{Maximum Flow} = \text{Minimum Cut}$

A minimum cut is a set of edges with the smallest total capacity that, if removed, disconnects $s$ from $t$.

Finding Minimum Cut

vector<pair<int, int>> minCut(int s, int t) {
    maxFlow(s, t);
    vector<bool> visited(n, false);
    queue<int> q;
    q.push(s);
    visited[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto& e : graph[u]) {
            if (e.cap > 0 && !visited[e.to]) {
                visited[e.to] = true;
                q.push(e.to);
            }
        }
    }
    vector<pair<int, int>> cutEdges;
    for (int u = 0; u < n; u++) {
        if (visited[u]) {
            for (auto& e : graph[u]) {
                if (!visited[e.to] && e.cap == 0) {
                    cutEdges.push_back({u, e.to});
                }
            }
        }
    }
    return cutEdges;
}

Applications

• Bipartite matching (using max flow)
• Edge-disjoint and vertex-disjoint paths
• Project selection problems

Complexity

Graph Type	Time Complexity
General	$O(V^2 E)$
Unit capacity	$O(E \sqrt{V})$
Bipartite/unit network	$O(E \sqrt{V})$

Comparison of Max Flow Algorithms

Algorithm	Time Complexity	Best For
Ford-Fulkerson	$O(E \cdot \text{maxFlow})$	Small flows
Edmonds-Karp	$O(VE^2)$	General
Dinic	$O(V^2 E)$	General, bipartite
Push-Relabel	$O(V^2 E)$ or $O(V^3)$	Dense graphs

Tips

1. Use the iter array in Dinic to avoid revisiting blocked edges in the same phase.
2. For unit capacity graphs, Dinic is very efficient.
3. For large capacities, consider capacity scaling.
4. For multiple sources/sinks, add a super source/sink.