↩ back to Network Flow

Dinic's Algorithm

Edmonds-Karp finds max flow by repeating the same move over and over: breadth-first search the whole residual graph for one shortest augmenting path, push flow along it, throw the search away, repeat. Dinic's algorithm is built on the same two ideas — residual graphs, shortest-path augmentation — but refuses to throw a BFS away after using it for only one path. Instead it builds a level graph: every node's BFS distance from the source, and only the edges that advance from level L to level L+1. Every S→T path through that level graph is automatically a shortest augmenting path, so instead of finding one and rebuilding, Dinic's finds every path it can inside that single level graph — a blocking flow — before paying for another BFS. The demo below reuses Edmonds-Karp's exact graph, so the two pages can be compared directly: same network, same final answer, fewer rebuilds.

A blocking flow is not the same thing as a max flow on the level graph's own subgraph of edges — it's a flow after which no further path exists using only level-graph edges, found by depth-first search that only ever steps from level L to L+1 and backtracks the instant a node has no such edge left with spare capacity. One structural fact makes this fast: a level graph is acyclic (edges only ever increase the level number), so a single DFS pass with a current-arc pointer per node — remember which edge index you left off at, and never rescan an edge already proven dead-end this phase — finds every path in the blocking flow without ever re-walking the same dead branch twice. See Pitfalls for what happens, concretely, if that pointer is dropped.

Try it

Same six nodes and eight directed edges as the Edmonds-Karp demo, labeled flow/capacity. Press Step or Run. Each phase starts with a breadth-first level assignment — every node gets a small level badge, and edges that don't advance exactly one level (already saturated, or connecting two nodes at the same level) turn dashed and dim, excluded from this phase's search. Within a phase, each step pushes flow along one level-graph path — black-bordered nodes and a thick black edge mark it, same convention as Edmonds-Karp — until no level-graph path remains and the next phase recomputes levels from scratch. When no level at all reaches T, the algorithm stops and reveals the minimum cut, exactly as Edmonds-Karp's demo does.

Why batching paths into phases is provably faster

Two facts, both about how the shortest augmenting path length behaves over the whole run, are what turn "batch paths by level before rebuilding" from a good idea into a proven O(V)-phase bound — the same two facts Edmonds-Karp's own complexity proof leans on, reused here for a stronger conclusion. First, the shortest augmenting path length never decreases from one phase to the next (pushing flow can only remove edges from the residual graph or add reverse ones that go the wrong way for a shorter path — it can never create a shortcut). Second, a full blocking flow strictly saturates at least one edge on every path through that phase's level graph, which forces the shortest path next phase to be strictly longer, not just different. Since path length is bounded by V, that caps the whole run at O(V) phases — regardless of how many individual augmenting paths those phases contain between them. Edmonds-Karp gets the same O(V)-ish bound on path length increases, but pays for a fresh O(E) BFS on every single augmenting path, not every phase; Dinic's pays that BFS cost once per phase and amortizes an unbounded number of paths across it. On the demo graph that's the difference between 3 BFS calls (Edmonds-Karp, one per path) and 2 (Dinic's, one per phase — phase 1 alone accounts for 2 of the 3 total paths).

Each phase's blocking flow itself costs O(VE) with the current-arc optimization: the DFS explores at most O(E) edges in total finding successful paths (each successful path is at most V edges long, and there are at most E augmentations per phase since each one saturates at least one new edge), plus O(VE) more for the current-arc pointers ensuring no dead edge is ever rescanned within the phase. Multiplied by O(V) phases, that's the O(V²E) total bound in the header above — a real asymptotic improvement over Edmonds-Karp's O(VE²) on graphs where V is smaller than E, which is most graphs worth calling sparse. The gap is bigger still on the unit- capacity graphs bipartite matching reduces to: Dinic's runs in O(E√V) there, a bound tight enough that it's the textbook default for matching problems specifically, not just a generic max-flow fallback.

Reference implementation

Matches the demo above one for one — same level-graph BFS, same current-arc blocking-flow DFS, just without the intermediate yield points the demo uses to show every path and every phase boundary:

function dinic(numNodes, edges, s, t) {
  const cap = Array.from({ length: numNodes }, () => new Array(numNodes).fill(0));
  edges.forEach(e => { cap[e.a][e.b] += e.cap; });
  const flow = Array.from({ length: numNodes }, () => new Array(numNodes).fill(0));
  let total = 0;

  while (true) {
    // Phase: assign every node its BFS distance from s.
    const level = new Array(numNodes).fill(-1);
    level[s] = 0;
    const queue = [s];
    while (queue.length) {
      const u = queue.shift();
      for (let v = 0; v < numNodes; v++) {
        if (level[v] === -1 && cap[u][v] - flow[u][v] > 0) {
          level[v] = level[u] + 1;
          queue.push(v);
        }
      }
    }
    if (level[t] === -1) break; // t unreachable at any length — done

    // Blocking flow: DFS restricted to level[v] === level[u] + 1, with a
    // current-arc pointer per node so no dead edge is ever rescanned.
    const arc = new Array(numNodes).fill(0);
    function dfs(u, pushed) {
      if (u === t) return pushed;
      for (; arc[u] < numNodes; arc[u]++) {
        const v = arc[u];
        if (level[v] === level[u] + 1 && cap[u][v] - flow[u][v] > 0) {
          const sent = dfs(v, Math.min(pushed, cap[u][v] - flow[u][v]));
          if (sent > 0) {
            flow[u][v] += sent;
            flow[v][u] -= sent; // opens the reverse residual edge
            return sent;
          }
        }
      }
      return 0;
    }
    let pushed;
    while ((pushed = dfs(s, Infinity)) > 0) total += pushed;
  }

  return total;
}

Pitfalls

Stopping after one blocking flow, without recomputing levels, understates the max flow — not a rounding error, a real shortfall. On this page's own demo graph, phase 1's blocking flow alone pushes 5 (S→A→C→T) + 8 (S→B→D→T) = 13. The true max flow is 15 — the extra 2 only appears in phase 2, once levels are recomputed and S→A→B→D→T becomes reachable in the new level graph. A blocking flow is only a stand-in for "shortest paths exhausted at the current level structure," never for "no augmenting path exists at all" — that second, stronger claim requires the next phase's BFS to actually fail to reach T, which is exactly the check phase 3 performs on this graph before the demo declares 15 final.

Dropping the current-arc pointer doesn't change the answer, only how much work it costs to get there — and the gap is real, not asymptotic hand-waving. A DFS that restarts its edge scan from index 0 on every call, instead of resuming from where it last left off, re-examines every dead-end branch it already ruled out earlier in the same phase. On a small constructed graph — a source with 5 genuine dead-end edges plus one real edge fanning out into 4 parallel unit-capacity paths to the sink — both versions correctly find the same max flow of 4, but a direct instrumented count of edge examinations during the blocking flow shows current-arc doing 138 versus the naive restart's 426, over 3× more, on a graph with only 12 nodes. The gap compounds with graph size: every one of the 4 successful augmentations re-pays the cost of re-discovering the same 5 dead ends, work the current-arc pointer only ever pays once total.

Reverse residual edges are still required, for the same reason Edmonds-Karp needs them. A level graph is built fresh from whatever the residual graph looks like at the start of each phase, and that residual graph only has the reverse edges flow has actually opened. Skip building them when pushing a blocking flow, and a phase can permanently lock in a combination of paths that blocks a strictly better one — the same failure mode Edmonds-Karp's own Pitfalls section demonstrates concretely on a small graph; nothing about batching augmentations into phases removes the need for that escape hatch.

The level graph is a different object every phase — don't reuse level numbers across phases. On this page's demo graph, node B is level 1 in phase 1 but level 2 in phase 2 (compare the two level badges directly in the Try It demo). A level graph answers "which edges are usable this phase," not a fact about the node — caching a level number across phases would silently corrupt the next phase's blocking flow, accepting or rejecting edges based on a distance that's no longer current.

Complexity

Time: O(V²E) for general graphs — O(V) phases (proven via the shortest-path-length argument above), each costing O(VE) for its BFS plus current-arc blocking flow. O(E√V) on unit-capacity graphs specifically (bipartite matching's reduction included), a tighter bound from a separate argument about how few phases a unit-capacity network can have before the remaining flow itself is bounded by √V. Either way, strictly better than Edmonds-Karp's O(VE²) whenever V < E. Space: O(V²) for the capacity/flow matrices as implemented here (or O(V + E) with adjacency lists), plus O(V) for the level array and current-arc pointers.

See Choosing a Network Flow Algorithm for how this compares against Edmonds-Karp and Push-Relabel side by side — including why this page's own O(E√V) unit-capacity bound makes it the better engine to back a Bipartite Matching reduction, not Edmonds-Karp.