DSA Graphs

Dinic's Algorithm

Why rebuild a full BFS for every tiny augmentation? Batch the work. Grow a , push a , then rebuild levels.

With , Dinic runs in O(V²E) and is often the sparse-graph default in contests and matching reductions.

Algorithm journey

BFS levels from s

Stop if t unreachable.

Only dist-advancing edges.

DFS/stack pushes until blocked.

Rebuild levels

Distances strictly increase for t.

What actually happens

Naive idea: Edmonds-Karp one path per BFS. Correct but pays a full BFS per augmentation.

Better idea: after one BFS, saturate all shortest paths via a blocking flow before rebuilding distances. Level of t rises each phase.

The improved design still fails if you forget current-edge pointers (quadratic blow-up inside a phase) or if the graph is extremely dense where push-relabel may win.

Invariant

Within a phase, only level edges are used. After a blocking flow, no s–t path remains in that level graph, so the next BFS gives a strictly larger dist[t] (or disconnects t).

How to choose Dinic

1. Sparse max-flow / bipartite matching? Strong default.

2. Unit networks? Even better specialized bounds.

3. Huge dense graphs? Benchmark push-relabel.

Quantitative check

O(V²E): V=500, E=2000 ⇒ ~5×10⁸ in the bound, often much faster in practice because phases are few. Unit-capacity networks can reach ~O(min(V^0.6666666666666666, E^0.5) E).

Interactive demo

Phase: 0

Max Flow: 0

Click Play to build level graph!

0SRC

5SINK

Source

Sink

Level Graph Edge

Current Path

Flow

🎯 Key Insight: Level Graphs

Dinic's builds a level graph using BFS, containing only edges from level i to i+1. Then it finds a blocking flow (saturates at least one edge on every path). After each blocking flow, the shortest path length increases, guaranteeing at most V phases!

🔑 Key Concepts

Level Graph

A subgraph containing only edges that go from level i to level i+1. Levels are determined by BFS distance from the source. This ensures we only use shortest paths in the current iteration.

Blocking Flow

A flow where every source-to-sink path in the current level graph has at least one saturated edge (residual capacity = 0). Once we find a blocking flow, we rebuild the level graph and repeat.

Distance Labeling

Each vertex gets a "level" or "distance" from the source. We only push flow along edges that increase the level by exactly 1, ensuring we always move closer to the sink.

One phase, three invariants

Level admissibility

DFS uses only positive-residual edges satisfying level[v] = level[u] + 1. The level graph is acyclic.

Current arc

Once an outgoing edge cannot send more in this phase, its pointer never moves backward. Edge scans are amortized across the blocking-flow search.

Phase progress

A blocking flow destroys every shortest residual path. The next reachable sink level therefore strictly increases.

Correctness bridge: when BFS can no longer label the sink, there is no augmenting path. Residual reachability then supplies a minimum cut, proving the accumulated flow is maximum.

🔍 Did You Know? Level Graph Property

After each blocking flow, the distance from source to sink in the level graph strictly increases! This means we can have at most V phases (where V is the number of vertices), because the shortest path can't exceed V-1 edges. This is the key to Dinic's polynomial time guarantee!

📝 Algorithm Steps

Build Level Graph (BFS)

Use BFS to assign levels to vertices based on shortest distance from source. Only include edges (u, v) where level[v] = level[u] + 1 and residual capacity > 0.

Find Blocking Flow (DFS)

Use DFS to find augmenting paths in the level graph and push flow until no more paths exist (blocking flow achieved). Use optimizations like "current arc" to avoid revisiting saturated edges.

Update Residual Graph

Update flow values and residual capacities based on the blocking flow found.

Repeat

Repeat steps 1-3 until BFS cannot reach the sink (no augmenting path exists).

🎯 Key Insight: Why O(V² E)?

Dinic's algorithm has at most V phases (level graph rebuilds) because the shortest path length increases each time. Each phase takes O(V E) time: O(E) for BFS to build the level graph, and O(V E) for finding the blocking flow with DFS. Total: O(V) × O(V E) = O(V² E)!

For unit capacity networks (all edges have capacity 1), this improves to O(E × min(V^(2/3), E^(1/2)))!

💻 Production-shaped adjacency-list implementation

Python

python

from collections import deque

class Edge:
    def __init__(self, to: int, rev: int, residual: int) -> None:
        self.to, self.rev, self.residual = to, rev, residual

class Dinic:
    def __init__(self, n: int) -> None:
        if n <= 0:
            raise ValueError("n must be positive")
        self.graph = [[] for _ in range(n)]

    def add_edge(self, u: int, v: int, capacity: int) -> None:
        if not (0 <= u < len(self.graph) and 0 <= v < len(self.graph)):
            raise IndexError("vertex out of range")
        if u == v:
            raise ValueError("self-loops are not supported")
        if capacity < 0:
            raise ValueError("capacity must be non-negative")
        forward = Edge(v, len(self.graph[v]), capacity)
        reverse = Edge(u, len(self.graph[u]), 0)
        self.graph[u].append(forward)
        self.graph[v].append(reverse)

    def _levels(self, source: int) -> list[int]:
        level = [-1] * len(self.graph)
        level[source] = 0
        queue = deque([source])
        while queue:
            u = queue.popleft()
            for edge in self.graph[u]:
                if edge.residual > 0 and level[edge.to] == -1:
                    level[edge.to] = level[u] + 1
                    queue.append(edge.to)
        return level

    def _send(self, u: int, sink: int, pushed: int,
              level: list[int], next_edge: list[int]) -> int:
        if u == sink:
            return pushed
        while next_edge[u] < len(self.graph[u]):
            edge = self.graph[u][next_edge[u]]
            if edge.residual > 0 and level[edge.to] == level[u] + 1:
                sent = self._send(edge.to, sink, min(pushed, edge.residual),
                                  level, next_edge)
                if sent:
                    edge.residual -= sent
                    self.graph[edge.to][edge.rev].residual += sent
                    return sent
            next_edge[u] += 1
        return 0

    def max_flow(self, source: int, sink: int) -> int:
        if not (0 <= source < len(self.graph) and 0 <= sink < len(self.graph)):
            raise IndexError("vertex out of range")
        if source == sink:
            raise ValueError("source and sink must differ")
        total = 0
        while True:
            level = self._levels(source)
            if level[sink] == -1:
                return total
            next_edge = [0] * len(self.graph)
            source_bound = sum(edge.residual for edge in self.graph[source])
            while source_bound > 0:
                sent = self._send(source, sink, source_bound, level, next_edge)
                if sent == 0:
                    break
                total += sent
                source_bound -= sent

flow = Dinic(6)
for edge in [
    (0,1,16), (0,2,13), (1,2,10), (2,1,4), (1,3,12),
    (2,4,14), (3,2,9), (4,3,7), (3,5,20), (4,5,4),
]:
    flow.add_edge(*edge)
assert flow.max_flow(0, 5) == 23

Java

java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Dinics {
    static final class Edge {
        final int to, rev;
        long residual;
        Edge(int to, int rev, long residual) {
            this.to = to; this.rev = rev; this.residual = residual;
        }
    }

    private final List<List<Edge>> graph;
    private final int[] level;
    private final int[] nextEdge;

    Dinics(int n) {
        if (n <= 0) throw new IllegalArgumentException("n must be positive");
        graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        level = new int[n];
        nextEdge = new int[n];
    }

    void addEdge(int u, int v, long capacity) {
        if (u < 0 || u >= graph.size() || v < 0 || v >= graph.size()) {
            throw new IndexOutOfBoundsException("vertex out of range");
        }
        if (u == v) throw new IllegalArgumentException("self-loop");
        if (capacity < 0) throw new IllegalArgumentException("negative capacity");
        Edge forward = new Edge(v, graph.get(v).size(), capacity);
        Edge reverse = new Edge(u, graph.get(u).size(), 0L);
        graph.get(u).add(forward);
        graph.get(v).add(reverse);
    }

    private boolean buildLevels(int source, int sink) {
        Arrays.fill(level, -1);
        level[source] = 0;
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.add(source);
        while (!queue.isEmpty()) {
            int u = queue.remove();
            for (Edge edge : graph.get(u)) {
                if (edge.residual > 0 && level[edge.to] == -1) {
                    level[edge.to] = level[u] + 1;
                    queue.add(edge.to);
                }
            }
        }
        return level[sink] != -1;
    }

    private long send(int u, int sink, long pushed) {
        if (u == sink) return pushed;
        while (nextEdge[u] < graph.get(u).size()) {
            Edge edge = graph.get(u).get(nextEdge[u]);
            if (edge.residual > 0 && level[edge.to] == level[u] + 1) {
                long sent = send(edge.to, sink, Math.min(pushed, edge.residual));
                if (sent != 0) {
                    edge.residual -= sent;
                    graph.get(edge.to).get(edge.rev).residual += sent;
                    return sent;
                }
            }
            nextEdge[u]++;
        }
        return 0L;
    }

    long maxFlow(int source, int sink) {
        if (source < 0 || source >= graph.size() || sink < 0 || sink >= graph.size()) {
            throw new IndexOutOfBoundsException("vertex out of range");
        }
        if (source == sink) throw new IllegalArgumentException("source == sink");
        long total = 0L;
        while (buildLevels(source, sink)) {
            Arrays.fill(nextEdge, 0);
            long sent;
            while ((sent = send(source, sink, Long.MAX_VALUE)) != 0L) {
                total = Math.addExact(total, sent);
            }
        }
        return total;
    }

    public static void main(String[] args) {
        Dinics flow = new Dinics(6);
        long[][] edges = {
            {0,1,16}, {0,2,13}, {1,2,10}, {2,1,4}, {1,3,12},
            {2,4,14}, {3,2,9}, {4,3,7}, {3,5,20}, {4,5,4}
        };
        for (long[] edge : edges) flow.addEdge((int) edge[0], (int) edge[1], edge[2]);
        if (flow.maxFlow(0, 5) != 23L) throw new AssertionError();
    }
}

⚡ Complexity Analysis

Time Complexity

•
O(V² E) general case
At most V phases, each taking O(V E)
•
O(E · min(V^(2/3), √E)) for unit-capacity networks
Bipartite matching admits the familiar O(E√V) specialization.
•
Faster than Edmonds-Karp for dense graphs
O(V² E) vs O(V E²)

Space Complexity

•
O(V + E)
Paired residual adjacency lists, including reverse edges
•
O(V) auxiliary
For level array and current arc pointers

💡 Pro Tip: Current Arc Optimization

The "current arc" optimization is crucial for Dinic's efficiency! Instead of checking all edges from a vertex every time, we remember which edge we last checked and continue from there. This prevents redundant checks of saturated edges and improves the blocking flow phase from O(V² E) to O(V E). Always implement this optimization!

✅ Pros & ❌ Cons

✅ Advantages

✓Batches all shortest residual paths within each phase
✓Excellent performance in practice
✓Works well for unit capacity networks
✓Relatively simple to implement
✓Polynomial time guarantee

❌ Limitations

✗More complex than Edmonds-Karp
✗Requires careful implementation of optimizations
✗Can be slower than Push-Relabel for very large graphs
✗Needs both BFS and DFS (more code)

When Dinic is the right tool

Workload	Why	Watch for
Bipartite matching	Unit capacities and shallow layered graphs	Hopcroft-Karp is more specialized and simpler for pure matching
Sparse general flow	Adjacency-list scans and effective path batching	Worst-case bound remains O(V²E)
Dense / huge instances	Still polynomial and predictable	A tuned highest-label Push-Relabel solver may win; benchmark
Deep path graph	Correct result	Recursive DFS may overflow Python/Java stacks; use an iterative blocking-flow routine

Implementation review checklist

• Append a distinct paired edge for every parallel or antiparallel input edge.
• Rebuild levels and reset current-arc pointers once per phase.
• Advance a pointer only after its edge cannot push more in that phase.
• Reject negative capacities, self-loops, and source == sink.
• Use Java long and checked total-flow addition.
• Test disconnected graphs, zero capacities, cancellation, and duplicate edges.
• Rebuild the one-shot residual object before a second max-flow query.

Postcondition: capacity and conservation hold, and residual reachability defines a cut whose original capacity equals the returned flow.

💼 Real World Applications

🌐 Network Routing

Internet service providers use Dinic's algorithm for optimizing data packet routing through network infrastructure, maximizing throughput between data centers.

Example: CDN traffic optimization

🎮 Game Theory

Used in competitive programming and game AI for solving bipartite matching problems and resource allocation puzzles.

Example: ACM ICPC problems

🚆 Transportation

Railway and airline companies use max flow algorithms to optimize passenger flow through transportation networks during peak hours.

Example: Metro system capacity planning

💧 Water Distribution

Municipal water systems use Dinic's algorithm to optimize water flow distribution, ensuring maximum delivery to all areas.

Example: City water supply optimization

💼 Real World Application: Competitive Programming

Dinic's algorithm is a favorite in competitive programming (Codeforces, TopCoder, ACM ICPC) because it's fast enough for most max flow problems while being simpler to implement than Push-Relabel. Many top competitive programmers have Dinic's as their go-to max flow template!

Short takeaway

Dinic batches shortest-path augmentations: build a level graph, push a blocking flow, rebuild. Current-edge pointers keep each phase efficient; O(V²E) is the standard bound.

Exercises

After a blocking flow, why must dist[t] increase on the next successful BFS?
What goes wrong if every DFS rescans adjacency lists from index 0 without a current-edge pointer?
Unit-capacity bipartite matching: why is Dinic often preferred over Edmonds-Karp?

Primary sources

Dinic, E. A. (1970): Algorithm for solution of a problem of maximum flow.
Cormen et al., CLRS / modern notes: blocking flows and level graphs.
Competitive programming references on Dinic with current-edge optimization.