Dinic's Algorithm

A Bit of History

The conceptual leap is batching. Edmonds–Karp pays for a BFS before every augmentation. Dinic pays for one BFS, then extracts as much flow as possible from all shortest residual routes before the next BFS.

Start With the Residual Network

Maximum-flow algorithms never reason only about the original capacities. They work in a residual graph, whose edge $u\to v$ stores how much additional flow may still be sent. If the original capacity is $c(u,v)$ and current flow is $f(u,v)$, then:

The reverse residual edge is the algorithm’s undo button: later paths may cancel or reroute earlier flow. Every augmentation by $\Delta$ updates the paired residual capacities as $r(u,v)\mathrel{-}=\Delta$ and $r(v,u)\mathrel{+}=\Delta$.

One Dinic Phase

1. BFS the residual graph. Assign $operatorname{level}[s]=0$ and discover every vertex reachable through positive-residual edges.
2. Keep only forward layers. DFS may traverse $u\to v$ only when $r(u,v)>0$ and $operatorname{level}[v]=\operatorname{level}[u]+1$.
3. Push until blocked. Repeated DFS calls send bottleneck flow. A current-edge pointer remembers which outgoing edges have already failed.
4. Rebuild or stop. Once no layered $s$–$t$ path remains, run BFS again. If BFS cannot reach $t$, the residual max-flow criterion proves optimality.

The Level Graph: A Temporary DAG

BFS assigns shortest residual distances. Keeping only edges that advance exactly one level makes the usable subgraph acyclic: every DFS step strictly increases the level. Sideways edges, backward edges, and edges that skip the required next level are ignored for this phase, not deleted from the residual network.

Blocking Flow: More Than One Path

A blocking flow does not necessarily saturate every edge in the level graph. It guarantees that every layered path from $s$ to $t$ contains at least one saturated edge. Consequently, the current level graph has no remaining augmenting path.

Visual Walkthrough: One Complete Phase

In this layered network, the sink-side capacities total $4+3=7$. DFS can distribute seven units across several routes. After that, both edges entering $t$ are saturated, so every layered $s$–$t$ path is blocked—even though the source still has unused outgoing capacity.

Correctness Intuition and Invariants

There are fewer than $V$ possible positive sink levels, so there are at most $V-1$ successful phases. When BFS finally leaves $t$ unreachable, the vertices reachable from $s$ define an $s$–$t$ cut with no positive residual edge crossing it. The current flow equals that cut’s capacity, establishing maximum flow by the max-flow/min-cut theorem.

Implementation

The compact listings below use a residual capacity matrix for readability. They correctly maintain reverse capacity and a per-vertex current-edge pointer, but scanning all $V$ possible destinations makes them best for learning or small dense graphs. For large sparse graphs, store explicit residual edge objects in adjacency lists so a phase scans actual edges rather than all vertex pairs.

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.
    """
    if source == sink:
        raise ValueError("source and sink must differ")
    capacity = [row[:] for row in capacity]  # preserve the caller's matrix
    flow_limit = sum(capacity[source])

    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, flow_limit, 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>
#include <algorithm>
#include <stdexcept>
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) {
    if (source == sink) throw invalid_argument("source and sink must differ");
    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) {
        if (source == sink) throw new IllegalArgumentException("source and sink must differ");
        n = nn;
        capacity = new int[n][];
        for (int i = 0; i < n; i++) capacity[i] = cap[i].clone();
        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
    }
}

Implementation checklist

Complexity Analysis

On an adjacency-list residual graph, BFS costs $O(E)$. A standard blocking-flow computation costs $O(VE)$ in the general analysis, and there are fewer than $V$ successful phases:

The code above uses matrices, so its scans are expressed in terms of $V^2$ possible arcs; the classic edge-sensitive bounds assume adjacency lists. Specialized networks admit stronger results: Dinic solves bipartite matching via the usual unit-capacity reduction in $O(E\sqrt V)$, matching the familiar Hopcroft–Karp phase bound. More general unit-capacity networks have related but subtler bounds; $O(E\sqrt V)$ should not be quoted for every unit-capacity graph without the needed structure.

When Should You Use Dinic?

Real-World Applications

The same reduction pattern appears in image segmentation, project selection, sports elimination, disjoint-path problems, and circulation models. The modeling step—choosing vertices, directions, and capacities—is often harder than running the algorithm.

Exercises

Limitations

Dinic remains valuable because its concepts line up cleanly with its implementation: residual pairs, BFS levels, admissible edges, DFS bottlenecks, and current-edge pruning. That makes it a strong default when you need more performance than Edmonds–Karp without moving to a substantially more complex solver.