Dinic's Algorithm

A Bit of History

Yefim Dinitz (also transliterated Dinic), then a young Soviet researcher, published this algorithm in 1970 — as previewed in the Edmonds-Karp deep dive, Dinitz had independently discovered the same BFS-based augmenting-path insight behind Edmonds-Karp's 1972 paper two years earlier, but Cold War-era communication barriers between Soviet and Western computer science delayed word of his result reaching the West for years. Dinitz's algorithm goes further than the basic Edmonds-Karp idea, though: rather than finding and augmenting a single shortest path per phase, it saturates an entire "blocking flow" across all shortest paths simultaneously, achieving a meaningfully better worst-case bound.

Working Principle

The algorithm alternates two steps, repeated in phases:

1. Build a level graph via a single BFS from the source, labeling every reachable vertex with its shortest-path distance (its "level") from the source, using only edges with remaining residual capacity. If the sink is unreachable, the algorithm terminates — the current flow is already maximum.
2. Find a blocking flow within this level graph — a flow such that every path from source to sink using only "level-respecting" edges (edges going from level \(i\) to level \(i+1\)) is saturated, typically found via repeated DFS that advances along level-respecting edges only, backtracking (and permanently pruning) whenever a dead end is hit.

After computing a blocking flow, the phase ends, the level graph is rebuilt from scratch on the updated residual graph, and the process repeats.

Worked Example

On a network where the source has two disjoint length-2 paths to the sink, a single Dinic's phase builds a level graph revealing both paths simultaneously (both ending at the sink at level 2), and the blocking-flow DFS step saturates both paths in that same phase — where Edmonds-Karp would need two separate phases, one BFS-search-and-augment per path. Once both length-2 paths are saturated, the next phase's BFS reveals only longer, level-3-or-more paths remain, if any — illustrating concretely how blocking flow captures multiple augmentations per phase that a plain shortest-augmenting-path approach would spread across several.

Why Phases Are Bounded

Just as in Edmonds-Karp, the shortest source-to-sink distance in the residual graph is non-decreasing across phases (augmenting along shortest paths can only ever add "backward" edges that lengthen future shortest paths, never shorten them). Dinic's algorithm strengthens this: since every phase computes a full blocking flow (not just one path), the shortest distance is guaranteed to strictly increase after each phase, not merely stay the same — and since the shortest distance is bounded by \(V\), there can be at most \(O(V)\) phases total.

Complexity Analysis

Each phase's BFS level-graph construction costs \(O(E)\), and computing a blocking flow within a single phase (using the DFS-with-pruning approach, where each edge is examined and permanently discarded at most once per phase) costs \(O(VE)\):

$$\text{Time: } O(V^2 E) \qquad \text{(general graphs)} \qquad O(E\sqrt{V}) \text{ (unit-capacity graphs, e.g. bipartite matching)}$$

The \(O(V^2E)\) general bound already improves meaningfully on Edmonds-Karp's \(O(VE^2)\) on many graphs, and the specialized unit-capacity bound \(O(E\sqrt{V})\) exactly matches the Hopcroft-Karp bound from an earlier deep dive — no coincidence, since Hopcroft-Karp is essentially Dinic's algorithm specialized to the unit-capacity bipartite matching reduction.

Implementation

from collections import deque

def dinic_max_flow(n, capacity, source, sink):
    """
    n: number of vertices. capacity: n x n matrix of edge capacities (0 if no edge).
    Returns the maximum flow from source to sink.
    """
    def bfs_level_graph():
        level = [-1] * n
        level[source] = 0
        q = deque([source])
        while q:
            u = q.popleft()
            for v in range(n):
                if capacity[u][v] > 0 and level[v] == -1:
                    level[v] = level[u] + 1
                    q.append(v)
        return level if level[sink] != -1 else None

    def dfs_blocking_flow(u, pushed, level, it):
        if u == sink or pushed == 0:
            return pushed
        while it[u] < n:
            v = it[u]
            if capacity[u][v] > 0 and level[v] == level[u] + 1:
                d = dfs_blocking_flow(v, min(pushed, capacity[u][v]), level, it)
                if d > 0:
                    capacity[u][v] -= d
                    capacity[v][u] += d
                    return d
            it[u] += 1
        return 0

    max_flow = 0
    while True:
        level = bfs_level_graph()
        if level is None:
            break
        it = [0] * n
        while True:
            pushed = dfs_blocking_flow(source, float('inf'), level, it)
            if pushed == 0:
                break
            max_flow += pushed

    return max_flow

capacity = [
    [0, 10, 10, 0, 0, 0],
    [0, 0, 2, 4, 8, 0],
    [0, 0, 0, 0, 9, 0],
    [0, 0, 0, 0, 0, 10],
    [0, 0, 0, 6, 0, 10],
    [0, 0, 0, 0, 0, 0],
]
print(dinic_max_flow(6, capacity, 0, 5))  # 19

#include <vector>
#include <queue>
#include <limits>
#include <iostream>
using namespace std;

int n;
vector<vector<int>> capacity_;
vector<int> level, it;

bool bfsLevelGraph(int source, int sink) {
    level.assign(n, -1);
    level[source] = 0;
    queue<int> q;
    q.push(source);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v = 0; v < n; v++) {
            if (capacity_[u][v] > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[sink] != -1;
}

int dfsBlockingFlow(int u, int sink, int pushed) {
    if (u == sink || pushed == 0) return pushed;
    for (; it[u] < n; it[u]++) {
        int v = it[u];
        if (capacity_[u][v] > 0 && level[v] == level[u] + 1) {
            int d = dfsBlockingFlow(v, sink, min(pushed, capacity_[u][v]));
            if (d > 0) {
                capacity_[u][v] -= d;
                capacity_[v][u] += d;
                return d;
            }
        }
    }
    return 0;
}

int dinicMaxFlow(int nn, vector<vector<int>> cap, int source, int sink) {
    n = nn; capacity_ = cap;
    int maxFlow = 0;
    while (bfsLevelGraph(source, sink)) {
        it.assign(n, 0);
        int pushed;
        while ((pushed = dfsBlockingFlow(source, sink, numeric_limits<int>::max())) > 0) {
            maxFlow += pushed;
        }
    }
    return maxFlow;
}

int main() {
    vector<vector<int>> capacity = {
        {0,10,10,0,0,0}, {0,0,2,4,8,0}, {0,0,0,0,9,0},
        {0,0,0,0,0,10}, {0,0,0,6,0,10}, {0,0,0,0,0,0}
    };
    cout << dinicMaxFlow(6, capacity, 0, 5) << endl;  // 19
    return 0;
}

import java.util.*;

class Dinic {
    static int n;
    static int[][] capacity;
    static int[] level, it;

    static boolean bfsLevelGraph(int source, int sink) {
        level = new int[n];
        Arrays.fill(level, -1);
        level[source] = 0;
        Deque<Integer> q = new ArrayDeque<>();
        q.add(source);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v = 0; v < n; v++) {
                if (capacity[u][v] > 0 && level[v] == -1) {
                    level[v] = level[u] + 1;
                    q.add(v);
                }
            }
        }
        return level[sink] != -1;
    }

    static int dfsBlockingFlow(int u, int sink, int pushed) {
        if (u == sink || pushed == 0) return pushed;
        for (; it[u] < n; it[u]++) {
            int v = it[u];
            if (capacity[u][v] > 0 && level[v] == level[u] + 1) {
                int d = dfsBlockingFlow(v, sink, Math.min(pushed, capacity[u][v]));
                if (d > 0) {
                    capacity[u][v] -= d;
                    capacity[v][u] += d;
                    return d;
                }
            }
        }
        return 0;
    }

    static int maxFlow(int nn, int[][] cap, int source, int sink) {
        n = nn; capacity = cap;
        int maxFlow = 0;
        while (bfsLevelGraph(source, sink)) {
            it = new int[n];
            int pushed;
            while ((pushed = dfsBlockingFlow(source, sink, Integer.MAX_VALUE)) > 0) {
                maxFlow += pushed;
            }
        }
        return maxFlow;
    }

    public static void main(String[] args) {
        int[][] capacity = {
            {0,10,10,0,0,0}, {0,0,2,4,8,0}, {0,0,0,0,9,0},
            {0,0,0,0,0,10}, {0,0,0,6,0,10}, {0,0,0,0,0,0}
        };
        System.out.println(maxFlow(6, capacity, 0, 5));  // 19
    }
}

Real-World Applications

Exercises

1. Trace through the worked example (two disjoint length-2 paths) by hand, confirming a single blocking-flow DFS saturates both paths in one phase.
2. Explain why the DFS-with-pruning approach to blocking flow costs \(O(VE)\) per phase, focusing on why each edge is only ever permanently discarded once.
3. Verify by hand that the shortest source-to-sink distance strictly increases across two consecutive phases on a small example graph.
4. Challenge: Research why Dinic's algorithm specializes to exactly Hopcroft-Karp's bound on unit-capacity bipartite graphs, connecting the "level graph" concept here to Hopcroft-Karp's "phase" concept from the earlier deep dive.

Limitations