CoreSource checked

Dinic's Algorithm

Computes maximum flow using level graphs and blocking flows.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Graph Traversal
Difficulty: Advanced
Family: Network Flow
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 2
Relationships: 5
Code example: Ready
Visualization: Ready

Overview

Dinic's algorithm alternates between BFS level graph construction and DFS-style blocking-flow searches, reducing repeated work compared with one-path augmentation.

Core Concepts

level graphblocking flowresidual capacityaugmenting path

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(E V^2)

Average

O(E V^2)

Worst

O(E V^2)

Space

O(V + E)

When to Use

Use it when a clear polynomial maximum-flow algorithm is needed.
Use it for flow networks where repeated blocking-flow phases are effective.
Use it as a practical default before more specialized max-flow algorithms.

When Not to Use

Avoid it when capacities or residual edges are not modeled explicitly.
Avoid it when a specialized bipartite matching algorithm is simpler.
Avoid recursive DFS implementations that can overflow on deep level graphs.

What It Does

Computes maximum flow
Builds level graphs and sends blocking flows

Use Cases

Maximum-flow problems
Bipartite matching reductions
Teaching level-graph flow methods

Inputs

Graph
Start nodes or query nodes
Traversal state

Outputs

Visited nodes
Derived graph relationships

Key Formulas (2)

Residual capacity

residual(u, v) = capacity(u, v) − flow(u, v)

residual(u, v) = capacity(u, v) - flow(u, v)

Shows how much additional flow can still be sent along an edge.

Admissible edge

level_[v] = level_[u] + 1

level[v] = level[u] + 1

Restricts blocking-flow searches to edges that advance through the level graph.

Pseudocode

1.Prepare the inputs and state needed for Dinic's Algorithm.
2.Apply the level graph step while the stopping condition has not been met.
3.Update intermediate state and discard invalid candidates.
4.Return visited nodes.

Canonical Example

Input: small s-t network with two disjoint capacity-1 paths
Output: max flow = 2
Explanation: The first level graph exposes both shortest augmenting paths, and the blocking flow saturates them together.

Implementation Notes

Use BFS from the source to build levels in the residual graph.
Use current-edge pointers during DFS to avoid repeatedly scanning saturated edges.
Stop when the sink is unreachable in the level graph.

Common Pitfalls

Sending DFS flow along edges that do not respect the level graph.
Forgetting to rebuild levels after a blocking-flow phase.
Not keeping reverse residual edges consistent.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Highlight active nodes, discovered edges, and the graph structure produced by each step.

Step 1 of 4: Prepare the inputs and state needed for Dinic's Algorithm.

graph-traversal-mechanism

Notes

Dinic's Algorithm operates in O(E V^2) time and O(V + E) space within the Network Flow family. Key governing relation: residual(u, v) = capacity(u, v) - flow(u, v). Often compared with Ford-Fulkerson and Edmonds-Karp.