Max flow (Dinic)

Deep dive

How it works

In: directed graph with integer capacities, a source s and a sink t · Out: the maximum flow value, the flow on each edge, and a minimum cut (the source side) · State: residual capacities and levels, kept after the call, so flow can be continued after edges are added · Cost: O(V²E) general; O(E √V) on unit-capacity bipartite graphs

1. Store each edge e with its reverse e ^ 1 (edges are added in pairs, so the pair index differs in the lowest bit). Pushing f on e adds f to cap[e ^ 1].
2. BFS from s over edges with cap > 0 and set level[v]. If t is unreachable, stop: the flow is maximal.
3. DFS from s, only along edges with level[v] = level[u] + 1 and cap > 0. Push the bottleneck. it[u] remembers the first edge of u not yet known to be saturated or dead, so no edge is retried within a phase.
4. Repeat until DFS finds no more paths, then go to step 2.
5. Min cut: after termination, S = vertices reachable from s in the residual graph. Cut edges are the original edges from S to V − S.

level 0   level 1   level 2   level 3
   s ───▶ a ───▶ c ───▶ t        DFS only moves right;
   └────▶ b ───▶ d ───┘          a → b (same level) is ignored this phase

Code

pub struct Dinic { adj: Vec<Vec<u32>>, to: Vec<u32>, cap: Vec<i64>, level: Vec<i32>, it: Vec<usize> }

impl Dinic {
    pub fn new(n: usize) -> Self {
        Dinic { adj: vec![vec![]; n], to: vec![], cap: vec![], level: vec![0; n], it: vec![0; n] }
    }

    /// Adds u -> v with capacity c (and rc for the reverse direction; 0 for a directed edge). Returns the edge id.
    pub fn add_edge(&mut self, u: usize, v: usize, c: i64, rc: i64) -> usize {
        let e = self.to.len();
        self.adj[u].push(e as u32); self.to.push(v as u32); self.cap.push(c);
        self.adj[v].push(e as u32 + 1); self.to.push(u as u32); self.cap.push(rc);
        e
    }

    fn bfs(&mut self, s: usize, t: usize) -> bool {
        self.level.iter_mut().for_each(|l| *l = -1);
        let mut q = std::collections::VecDeque::from([s]);
        self.level[s] = 0;
        while let Some(u) = q.pop_front() {
            for &e in &self.adj[u] {
                let v = self.to[e as usize] as usize;
                if self.cap[e as usize] > 0 && self.level[v] < 0 { self.level[v] = self.level[u] + 1; q.push_back(v); }
            }
        }
        self.level[t] >= 0
    }

    fn dfs(&mut self, u: usize, t: usize, f: i64) -> i64 {
        if u == t { return f; }
        while self.it[u] < self.adj[u].len() {
            let e = self.adj[u][self.it[u]] as usize;
            let v = self.to[e] as usize;
            if self.cap[e] > 0 && self.level[v] == self.level[u] + 1 {
                let d = self.dfs(v, t, f.min(self.cap[e]));
                if d > 0 { self.cap[e] -= d; self.cap[e ^ 1] += d; return d; }
            }
            self.it[u] += 1; // edge saturated or leads to a dead end: never retry it this phase
        }
        0
    }

    pub fn max_flow(&mut self, s: usize, t: usize) -> i64 {
        let mut flow = 0;
        while self.bfs(s, t) {
            self.it.iter_mut().for_each(|i| *i = 0);
            loop { let f = self.dfs(s, t, i64::MAX); if f == 0 { break; } flow += f; }
        }
        flow
    }

    /// After max_flow: true for vertices on the source side of a minimum cut.
    pub fn min_cut_side(&self) -> Vec<bool> { self.level.iter().map(|&l| l >= 0).collect() }

    /// Flow currently on edge id e (as returned by add_edge with rc = 0).
    pub fn flow(&self, e: usize) -> i64 { self.cap[e ^ 1] }
}

Complexity and constants

• O(V² E) worst case: at most V − 1 phases, each O(VE) thanks to current arcs. Real graphs need far fewer phases, often order of 10-100.
• Unit capacities: O(E min(V^(2/3), √E)). Unit-capacity bipartite matching: O(E √V).
• With capacity scaling (only edges with cap ≥ Δ, halving Δ): O(V E log U) for max capacity U.
• Memory: about 16-24 B per edge pair here (two targets, two capacities, two adjacency slots). Use a CSR layout for graphs above about 10⁶ edges.
• Matching 10⁵ × 10⁵ vertices with order of 10⁶ edges takes well under a second.

Efficiency

• Cost: measured with the code above on an Apple M4 Pro, one thread: bipartite matching with 10^5 left and 10^5 right vertices and 10^6 random edges (flow 99,993) takes 389 ms in max_flow, plus 31 ms to build the graph. Memory about 16-24 B per edge pair (Complexity and constants). Bound: pointer-chasing over residual edges and cache misses.
• Levers:
  • current-arc pointer per vertex — keeps a phase at O(VE) instead of retrying dead edges (Complexity and constants; Pitfalls) — always
  • CSR layout instead of per-vertex vectors — contiguous arcs, fewer cache misses (Complexity and constants) — graphs above about 10^6 edges
  • capacity scaling — O(V E log U) for max capacity U (Complexity and constants) — large capacity ranges
  • continue from the current flow after adding edges or raising capacities (Implementation notes) — repeated or incremental queries
  • push-relabel or Boykov-Kolmogorov — often the fastest on large hard instances and vision grids (Variants; Boykov, Kolmogorov 2004) — dense graphs, image grids
• Naive → standard → state of the art:
  • Ford-Fulkerson with arbitrary augmenting paths · pseudo-polynomial in the flow value (Ford, Fulkerson 1956)
  • Edmonds-Karp (BFS paths) · O(V E²); Dinic with current arcs (code above) · O(V²E), 389 ms on the matching above
  • push-relabel with highest-label, gap and global relabeling · O(V²√E); Boykov-Kolmogorov on grid graphs in vision

Implementation notes

• Recursion depth is at most the s-t distance, which is small for matching graphs but up to V on long chains. Use an explicit stack in that case.
• Bipartite matching: s → each left vertex (cap 1 or its quota), left → right (cap 1), right → t (cap 1 or its quota). Matched pairs are left → right edges with flow == 1.
• Vertex capacities: split v into v_in → v_out with the vertex capacity.
• Undirected edges: add_edge(u, v, c, c). Both directions share one residual pair.
• Lower bounds / circulations: transform with a super source and super sink to check feasibility first.
• Incremental reuse: after adding edges or raising capacities, continue from the current flow instead of starting over.

Pitfalls

• Dropping the current-arc pointer (restarting each DFS at edge 0): correct results but exponential-looking slowdowns on dense graphs.
• Forgetting reverse edges: greedy augmenting without undo gets stuck below the maximum.
• Capacity overflow: use i64, and a finite "infinity" (sum of capacities + 1) for edges that must never be cut.
• Reading the min cut from level before max_flow has finished (the last BFS must be the one that failed to reach t).
• Floating capacities: tolerance issues and possible non-termination. Scale to integers.

Variants and alternatives

In production

Optimization and graph libraries: Google OR-Tools (max_flow, push-relabel), Boost Graph Library (push-relabel, Boykov-Kolmogorov, Edmonds-Karp), LEMON, NetworkX. Vision and imaging: OpenCV GrabCut (graph cuts for segmentation) and medical-imaging segmentation tools built on graph cuts (Boykov, Jolly 2001). Cluster scheduling: Quincy and the Firmament scheduler (min-cost flow placement; Isard et al. 2009, Gog et al. 2016).

Implementations

Sources

• E. A. Dinitz, Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation, Soviet Math. Doklady, 1970.
• L. Ford, D. Fulkerson, Maximal Flow Through a Network, Canadian Journal of Mathematics, 1956. paper
• J. Edmonds, R. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, JACM, 1972. paper
• S. Even, R. Tarjan, Network Flow and Testing Graph Connectivity, SIAM Journal on Computing, 1975. paper
• J. Hopcroft, R. Karp, An n^(5/2) Algorithm for Maximum Matchings in Bipartite Graphs, SIAM Journal on Computing, 1973. paper
• A. Goldberg, R. Tarjan, A New Approach to the Maximum-Flow Problem, JACM, 1988. paper
• Y. Boykov, V. Kolmogorov, An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision, IEEE PAMI, 2004. paper
• I. Gog, M. Schwarzkopf, A. Gleave, R. Watson, S. Hand, Firmament: Fast, Centralized Cluster Scheduling at Scale, OSDI, 2016. paper
• M. Isard, V. Prabhakaran, J. Currey, U. Wieder, K. Talwar, A. Goldberg, Quincy: Fair Scheduling for Distributed Computing Clusters, SOSP 2009. paper
• A. Schrijver, On the History of the Transportation and Maximum Flow Problems, Mathematical Programming 91(3), 2002. paper