Dinic's Algorithm

Introduction

Imagine water flowing through a network of pipes. Each pipe has a limited capacity, and you want to pump as much water as possible from a source to a sink. This is the maximum-flow problem, and it sits at the heart of logistics, chip design, image segmentation, and a dozen other fields.

The earliest algorithms — Ford–Fulkerson (1956) and Edmonds–Karp (1972) — found augmenting paths one at a time. They work, but they can be slow: Ford–Fulkerson can take a number of steps proportional to the total flow value, which may be enormous.

In 1970, a Soviet undergraduate named Yefim Dinic published a two-stage idea that changed everything. Instead of hunting for one path at a time, his algorithm first layers the entire graph with a BFS (producing a level graph where every edge strictly goes one level deeper), then floods that level graph all at once with a single blocking flow pass. Repeat until no more layering is possible — and the maximum flow is in hand.

The result: a provably $O(V^2 E)$ algorithm, where V is the number of vertices and E the number of edges. In practice it is often much faster, and on unit-capacity graphs it drops to a remarkable $O(E\sqrt{V})$ . It remains one of the most elegant examples of "structure the problem first, then solve" in all of algorithmics — a principle you will also meet in P vs NP when researchers study what makes problems tractable.

Try It

Below is a small flow network. Source is node 0, Sink is node 5. Each edge shows its capacity. Click Run BFS Phase to build the level graph (nodes colour by depth), then Push Blocking Flow to saturate every shortest path in one DFS sweep, and finally Run Full Dinic to watch the entire algorithm converge to the maximum flow.

<p class="hint">A flow network: <b>Source (S)</b> is node 0, <b>Sink (T)</b> is node 5.
    Each edge label shows <b>flow / capacity</b>. Use the buttons to step through Dinic's
    two-phase loop: BFS builds the level graph, DFS pushes a blocking flow.</p>
<div id="canvas-wrap"><canvas id="canvas" width="560" height="300"></canvas></div>
<div class="status" id="status">Press a button to begin.</div>
<div class="btns">
  <button id="bfs" type="button">Run BFS Phase</button>
  <button id="dfs" type="button">Push Blocking Flow</button>
  <button id="full" type="button">Run Full Dinic</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div id="info"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#canvas-wrap { overflow-x: auto; }
canvas { display: block; max-width: 100%; background: #f4f7fa; border-radius: 10px; border: 1px solid #d0dae3; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0 .3rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d4e89; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .45rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
#info { font-size: .82rem; color: #555; margin-top: .5rem; line-height: 1.6; min-height: 1.4em; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Graph definition ──────────────────────────────────────────────────────
// 6 nodes: 0=S, 1, 2, 3, 4, 5=T
// Adjacency with capacities; we maintain a residual graph.
const N = 6;
const LABELS = ['S','1','2','3','4','T'];
// Each edge: [u, v, capacity]
const EDGES_INIT = [
  [0,1,10],[0,2,10],
  [1,3,4],[1,2,2],[1,4,8],
  [2,4,9],
  [3,5,10],
  [4,3,6],[4,5,10]
];
// Node positions (x, y) on 560×300 canvas
const POS = [
  [60,150],   // S
  [190,60],   // 1
  [190,240],  // 2
  [370,60],   // 3
  [370,240],  // 4
  [500,150]   // T
];

// Residual graph: cap[u][v] = remaining capacity on u→v
let cap, flow, level, iter;

function initGraph() {
  cap = Array.from({length:N}, () => new Array(N).fill(0));
  flow = Array.from({length:N}, () => new Array(N).fill(0));
  level = new Array(N).fill(-1);
  iter = new Array(N).fill(0);
  for (const [u,v,c] of EDGES_INIT) {
    cap[u][v] += c;
    // reverse edge starts at 0
  }
}

// BFS to assign levels; returns true if sink reachable
function bfs() {
  level.fill(-1);
  const q = [0];
  level[0] = 0;
  while (q.length) {
    const u = q.shift();
    for (let v = 0; v < N; v++) {
      if (level[v] < 0 && cap[u][v] - flow[u][v] > 0) {
        level[v] = level[u] + 1;
        q.push(v);
      }
    }
  }
  return level[N-1] >= 0;
}

// DFS blocking flow: returns flow pushed from u to sink with limit f
function dfs(u, pushed) {
  if (u === N-1) return pushed;
  for (; iter[u] < N; iter[u]++) {
    const v = iter[u];
    const res = cap[u][v] - flow[u][v];
    if (res > 0 && level[v] === level[u] + 1) {
      const d = dfs(v, Math.min(pushed, res));
      if (d > 0) {
        flow[u][v] += d;
        flow[v][u] -= d;
        return d;
      }
    }
  }
  return 0;
}

// Run one full Dinic iteration (BFS + blocking flow loop)
function dinicPhase() {
  if (!bfs()) return 0;
  iter.fill(0);
  let total = 0, f;
  while ((f = dfs(0, Infinity)) > 0) total += f;
  return total;
}

// ── Drawing ───────────────────────────────────────────────────────────────
const LEVEL_COLORS = ['#e63946','#e07b25','#2a9d8f','#457b9d','#6a4c93','#0a7d33'];
const NODE_DEFAULT = '#1d3557';

function drawArrow(ctx, x1,y1,x2,y2, color, width) {
  const dx=x2-x1, dy=y2-y1, len=Math.sqrt(dx*dx+dy*dy);
  const ux=dx/len, uy=dy/len;
  const R=22; // node radius
  const sx=x1+ux*R, sy=y1+uy*R;
  const ex=x2-ux*R, ey=y2-uy*R;
  ctx.beginPath();
  ctx.moveTo(sx,sy);
  ctx.lineTo(ex,ey);
  ctx.strokeStyle=color; ctx.lineWidth=width;
  ctx.stroke();
  // arrowhead
  const angle=Math.atan2(ey-sy,ex-sx);
  const hs=9;
  ctx.beginPath();
  ctx.moveTo(ex,ey);
  ctx.lineTo(ex-hs*Math.cos(angle-0.4),ey-hs*Math.sin(angle-0.4));
  ctx.lineTo(ex-hs*Math.cos(angle+0.4),ey-hs*Math.sin(angle+0.4));
  ctx.closePath(); ctx.fillStyle=color; ctx.fill();
}

function render() {
  const canvas = document.getElementById('canvas');
  const ctx = canvas.getContext('2d');
  ctx.clearRect(0,0,canvas.width,canvas.height);

  // Draw edges
  for (const [u,v,c] of EDGES_INIT) {
    const [x1,y1]=POS[u], [x2,y2]=POS[v];
    const f = flow[u][v];
    const onLevelGraph = (level[u]>=0 && level[v]===level[u]+1 && cap[u][v]-flow[u][v]>0);
    const color = onLevelGraph ? '#e07b25' : '#adb5bd';
    const width = onLevelGraph ? 2.5 : 1.5;
    drawArrow(ctx, x1,y1,x2,y2, color, width);
    // label: flow/cap at midpoint
    const mx=(x1+x2)/2, my=(y1+y2)/2;
    ctx.font = '12px ui-monospace, monospace';
    ctx.fillStyle = '#333';
    ctx.textAlign='center'; ctx.textBaseline='middle';
    ctx.fillText(`${Math.max(0,f)}/${c}`, mx+6, my-9);
  }

  // Draw nodes
  for (let i=0;i<N;i++) {
    const [x,y]=POS[i];
    ctx.beginPath();
    ctx.arc(x,y,22,0,2*Math.PI);
    const lv = level[i];
    const col = (lv>=0 && lv<LEVEL_COLORS.length) ? LEVEL_COLORS[lv] : NODE_DEFAULT;
    ctx.fillStyle = col;
    ctx.fill();
    ctx.strokeStyle='#fff'; ctx.lineWidth=2; ctx.stroke();
    ctx.font='bold 14px system-ui,sans-serif';
    ctx.fillStyle='#fff'; ctx.textAlign='center'; ctx.textBaseline='middle';
    ctx.fillText(LABELS[i],x,y);
    if (lv>=0) {
      ctx.font='10px system-ui,sans-serif';
      ctx.fillStyle=col;
      ctx.fillText('L'+lv, x, y+32);
    }
  }
}

function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+(cls||''); }
function setInfo(t){ document.getElementById('info').textContent=t; }

function totalFlow() {
  let f=0; for(let v=0;v<N;v++) f+=Math.max(0,flow[0][v]); return f;
}

// ── Button handlers ───────────────────────────────────────────────────────
document.getElementById('bfs').addEventListener('click', () => {
  const ok = bfs();
  render();
  if (ok) {
    setStatus('BFS complete — nodes coloured by level (orange edges = level graph).','info');
    setInfo('Level graph edges (orange) are the only edges DFS will use in the next blocking-flow phase.');
  } else {
    setStatus(fmt('Sink is not reachable — max flow reached: %totalFlow%', { totalFlow: totalFlow() }),'ok');
    setInfo('No augmenting path exists; Dinic terminates.');
  }
});

document.getElementById('dfs').addEventListener('click', () => {
  if (level[N-1] < 0) { setStatus('Run BFS first.','bad'); return; }
  iter.fill(0);
  let pushed=0, f;
  while ((f=dfs(0,Infinity))>0) pushed+=f;
  level.fill(-1); // clear levels after blocking flow
  render();
  setStatus(fmt('Blocking flow pushed: +%pushed% units. Total so far: %totalFlow%.', { pushed: pushed, totalFlow: totalFlow() }),'info');
  setInfo('All shortest augmenting paths saturated. Run BFS again for the next phase.');
});

document.getElementById('full').addEventListener('click', () => {
  initGraph();
  let phases=0, total=0, f;
  while ((f=dinicPhase())>0) { total+=f; phases++; }
  level.fill(-1);
  render();
  setStatus(fmt('Max flow = %total% (found in%phases% %v%).', { total: total, phases: phases, v: phases!==1?'phases':'phase' }),'ok');
  setInfo('Dinic finished. Each phase strictly increased the shortest-path distance S→T, guaranteeing termination in at most V−1 = 5 phases.');
  console.log('Dinic max flow:', total, 'phases:', phases);
});

document.getElementById('reset').addEventListener('click', () => {
  initGraph();
  render();
  setStatus('Press a button to begin.');
  setInfo('');
});

// ── Init ──────────────────────────────────────────────────────────────────
initGraph();
render();

<p class="hint">A flow network: <b>Source (S)</b> is node 0, <b>Sink (T)</b> is node 5.
    Each edge label shows <b>flow / capacity</b>. Use the buttons to step through Dinic's
    two-phase loop: BFS builds the level graph, DFS pushes a blocking flow.</p>
<div id="canvas-wrap"><canvas id="canvas" width="560" height="300"></canvas></div>
<div class="status" id="status">Press a button to begin.</div>
<div class="btns">
  <button id="bfs" type="button">Run BFS Phase</button>
  <button id="dfs" type="button">Push Blocking Flow</button>
  <button id="full" type="button">Run Full Dinic</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div id="info"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#canvas-wrap { overflow-x: auto; }
canvas { display: block; max-width: 100%; background: #f4f7fa; border-radius: 10px; border: 1px solid #d0dae3; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0 .3rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d4e89; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .45rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
#info { font-size: .82rem; color: #555; margin-top: .5rem; line-height: 1.6; min-height: 1.4em; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Graph definition ──────────────────────────────────────────────────────
// 6 nodes: 0=S, 1, 2, 3, 4, 5=T
// Adjacency with capacities; we maintain a residual graph.
const N = 6;
const LABELS = ['S','1','2','3','4','T'];
// Each edge: [u, v, capacity]
const EDGES_INIT = [
  [0,1,10],[0,2,10],
  [1,3,4],[1,2,2],[1,4,8],
  [2,4,9],
  [3,5,10],
  [4,3,6],[4,5,10]
];
// Node positions (x, y) on 560×300 canvas
const POS = [
  [60,150],   // S
  [190,60],   // 1
  [190,240],  // 2
  [370,60],   // 3
  [370,240],  // 4
  [500,150]   // T
];

// Residual graph: cap[u][v] = remaining capacity on u→v
let cap, flow, level, iter;

function initGraph() {
  cap = Array.from({length:N}, () => new Array(N).fill(0));
  flow = Array.from({length:N}, () => new Array(N).fill(0));
  level = new Array(N).fill(-1);
  iter = new Array(N).fill(0);
  for (const [u,v,c] of EDGES_INIT) {
    cap[u][v] += c;
    // reverse edge starts at 0
  }
}

// BFS to assign levels; returns true if sink reachable
function bfs() {
  level.fill(-1);
  const q = [0];
  level[0] = 0;
  while (q.length) {
    const u = q.shift();
    for (let v = 0; v < N; v++) {
      if (level[v] < 0 && cap[u][v] - flow[u][v] > 0) {
        level[v] = level[u] + 1;
        q.push(v);
      }
    }
  }
  return level[N-1] >= 0;
}

// DFS blocking flow: returns flow pushed from u to sink with limit f
function dfs(u, pushed) {
  if (u === N-1) return pushed;
  for (; iter[u] < N; iter[u]++) {
    const v = iter[u];
    const res = cap[u][v] - flow[u][v];
    if (res > 0 && level[v] === level[u] + 1) {
      const d = dfs(v, Math.min(pushed, res));
      if (d > 0) {
        flow[u][v] += d;
        flow[v][u] -= d;
        return d;
      }
    }
  }
  return 0;
}

// Run one full Dinic iteration (BFS + blocking flow loop)
function dinicPhase() {
  if (!bfs()) return 0;
  iter.fill(0);
  let total = 0, f;
  while ((f = dfs(0, Infinity)) > 0) total += f;
  return total;
}

// ── Drawing ───────────────────────────────────────────────────────────────
const LEVEL_COLORS = ['#e63946','#e07b25','#2a9d8f','#457b9d','#6a4c93','#0a7d33'];
const NODE_DEFAULT = '#1d3557';

function drawArrow(ctx, x1,y1,x2,y2, color, width) {
  const dx=x2-x1, dy=y2-y1, len=Math.sqrt(dx*dx+dy*dy);
  const ux=dx/len, uy=dy/len;
  const R=22; // node radius
  const sx=x1+ux*R, sy=y1+uy*R;
  const ex=x2-ux*R, ey=y2-uy*R;
  ctx.beginPath();
  ctx.moveTo(sx,sy);
  ctx.lineTo(ex,ey);
  ctx.strokeStyle=color; ctx.lineWidth=width;
  ctx.stroke();
  // arrowhead
  const angle=Math.atan2(ey-sy,ex-sx);
  const hs=9;
  ctx.beginPath();
  ctx.moveTo(ex,ey);
  ctx.lineTo(ex-hs*Math.cos(angle-0.4),ey-hs*Math.sin(angle-0.4));
  ctx.lineTo(ex-hs*Math.cos(angle+0.4),ey-hs*Math.sin(angle+0.4));
  ctx.closePath(); ctx.fillStyle=color; ctx.fill();
}

function render() {
  const canvas = document.getElementById('canvas');
  const ctx = canvas.getContext('2d');
  ctx.clearRect(0,0,canvas.width,canvas.height);

  // Draw edges
  for (const [u,v,c] of EDGES_INIT) {
    const [x1,y1]=POS[u], [x2,y2]=POS[v];
    const f = flow[u][v];
    const onLevelGraph = (level[u]>=0 && level[v]===level[u]+1 && cap[u][v]-flow[u][v]>0);
    const color = onLevelGraph ? '#e07b25' : '#adb5bd';
    const width = onLevelGraph ? 2.5 : 1.5;
    drawArrow(ctx, x1,y1,x2,y2, color, width);
    // label: flow/cap at midpoint
    const mx=(x1+x2)/2, my=(y1+y2)/2;
    ctx.font = '12px ui-monospace, monospace';
    ctx.fillStyle = '#333';
    ctx.textAlign='center'; ctx.textBaseline='middle';
    ctx.fillText(`${Math.max(0,f)}/${c}`, mx+6, my-9);
  }

  // Draw nodes
  for (let i=0;i<N;i++) {
    const [x,y]=POS[i];
    ctx.beginPath();
    ctx.arc(x,y,22,0,2*Math.PI);
    const lv = level[i];
    const col = (lv>=0 && lv<LEVEL_COLORS.length) ? LEVEL_COLORS[lv] : NODE_DEFAULT;
    ctx.fillStyle = col;
    ctx.fill();
    ctx.strokeStyle='#fff'; ctx.lineWidth=2; ctx.stroke();
    ctx.font='bold 14px system-ui,sans-serif';
    ctx.fillStyle='#fff'; ctx.textAlign='center'; ctx.textBaseline='middle';
    ctx.fillText(LABELS[i],x,y);
    if (lv>=0) {
      ctx.font='10px system-ui,sans-serif';
      ctx.fillStyle=col;
      ctx.fillText('L'+lv, x, y+32);
    }
  }
}

function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+(cls||''); }
function setInfo(t){ document.getElementById('info').textContent=t; }

function totalFlow() {
  let f=0; for(let v=0;v<N;v++) f+=Math.max(0,flow[0][v]); return f;
}

// ── Button handlers ───────────────────────────────────────────────────────
document.getElementById('bfs').addEventListener('click', () => {
  const ok = bfs();
  render();
  if (ok) {
    setStatus('BFS complete — nodes coloured by level (orange edges = level graph).','info');
    setInfo('Level graph edges (orange) are the only edges DFS will use in the next blocking-flow phase.');
  } else {
    setStatus(fmt('Sink is not reachable — max flow reached: %totalFlow%', { totalFlow: totalFlow() }),'ok');
    setInfo('No augmenting path exists; Dinic terminates.');
  }
});

document.getElementById('dfs').addEventListener('click', () => {
  if (level[N-1] < 0) { setStatus('Run BFS first.','bad'); return; }
  iter.fill(0);
  let pushed=0, f;
  while ((f=dfs(0,Infinity))>0) pushed+=f;
  level.fill(-1); // clear levels after blocking flow
  render();
  setStatus(fmt('Blocking flow pushed: +%pushed% units. Total so far: %totalFlow%.', { pushed: pushed, totalFlow: totalFlow() }),'info');
  setInfo('All shortest augmenting paths saturated. Run BFS again for the next phase.');
});

document.getElementById('full').addEventListener('click', () => {
  initGraph();
  let phases=0, total=0, f;
  while ((f=dinicPhase())>0) { total+=f; phases++; }
  level.fill(-1);
  render();
  setStatus(fmt('Max flow = %total% (found in%phases% %v%).', { total: total, phases: phases, v: phases!==1?'phases':'phase' }),'ok');
  setInfo('Dinic finished. Each phase strictly increased the shortest-path distance S→T, guaranteeing termination in at most V−1 = 5 phases.');
  console.log('Dinic max flow:', total, 'phases:', phases);
});

document.getElementById('reset').addEventListener('click', () => {
  initGraph();
  render();
  setStatus('Press a button to begin.');
  setInfo('');
});

// ── Init ──────────────────────────────────────────────────────────────────
initGraph();
render();

Result

Console

Notice the two-phase rhythm: BFS assigns levels so that flow can only travel "downhill" (source → sink gets one level closer each step). The DFS then pushes as much flow as possible along every shortest path simultaneously — the blocking flow. After each round the shortest-path distance from source to sink strictly increases, so after at most $V-1$ rounds the algorithm terminates with the true maximum flow.

The Real Complexity

Why is Dinic's algorithm fast? The key is the level graph invariant.

BFS layering (O(E) per phase): a BFS from the source assigns each node a level (its shortest-path distance). Only edges that go from level $\ell$ to level $\ell+1$ enter the level graph. This takes O(E) time.
Blocking flow (O(VE) per phase): a DFS saturates every shortest augmenting path. Because the DFS advances only along level-graph edges and retreats (and removes dead-end edges) when stuck, each edge is visited at most twice — giving O(VE) per phase.
Number of phases is O(V): after each blocking flow, the shortest-path distance from source to sink strictly increases by at least 1. Since that distance is at most $V-1$ , there are at most $V-1$ phases.
Total: $O(V) \times O(VE) = O(V^2 E)$ . This was a major advance over Edmonds–Karp's $O(VE^2)$ .

Bonus for unit graphs. When every edge capacity is 1 (or bounded by a constant), the number of phases drops to $O(\sqrt{E})$ , yielding total time $O(E\sqrt{E}) = O(E^{3/2})$ — or $O(E\sqrt{V})$ on sparse graphs. This makes Dinic the algorithm of choice for bipartite matching and many combinatorial problems.

Dinic's result is proven and exact — not an open question like P vs NP. His 1970 paper (published in Soviet journals and later widely translated) closed the question of how fast max-flow could be done with the tools available then, and sparked decades of follow-up: the push-relabel algorithm (Goldberg–Tarjan, 1988) achieves $O(V^2\sqrt{E})$ on general graphs, but Dinic's blocking-flow structure remains the cleanest route to understand why max-flow is polynomially solvable.

Where It Matters

Maximum flow is one of the most reused subroutines in all of computing, and Dinic's algorithm is the standard workhorse:

Network routing: traffic engineering in backbone internet routers computes max-flow to decide how to split packets across links without exceeding link capacities.
Bipartite matching: finding the largest matching in a bipartite graph reduces to max-flow on a unit-capacity network. Dinic's O(E√V) bound for unit graphs means it handles millions of edges in seconds — used in job-scheduling and ride-sharing assignments.
Image segmentation (s-t cuts): the max-flow min-cut theorem says the maximum flow equals the minimum cut. Computer vision uses this to separate foreground from background in an image by finding the cheapest set of pixel-boundary edges to sever.
Supply-chain and logistics: rail or road networks modelled as capacitated graphs use Dinic to find bottlenecks and plan capacity upgrades.
Compiler register allocation: interference graphs in compilers are sometimes handled with flow-based methods that invoke Dinic internally.

The unifying theme: any time you need to push as much "stuff" as possible through a network with limited edges, you are looking at a max-flow problem — and Dinic's two-phase loop is almost certainly the algorithm quietly doing the work.

Conclusion

Dinic's algorithm is a masterclass in "structure before search." Instead of blindly hunting for augmenting paths, it first imposes a clean layered order on the graph, then exploits that order to saturate all shortest paths at once. The result — $O(V^2 E)$ , or $O(E\sqrt{V})$ on unit graphs — transformed network flow from a theoretical curiosity into a practical tool used billions of times a day.

The deeper lesson is one you will find throughout complexity theory: the right structural decomposition often does more work than clever search ever could. That same spirit drives the level hierarchies in P vs NP research and the layered proofs behind problems like max matching. Dinic gave us not just an algorithm, but a blueprint for how to think about flow.

Comments

Loading comments...

https://www.kipuhub.com/en/article/dinic-algorithm/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Layer first, flood second — and finish in $O(V^2 E)$