Home▸Algorithms & AI▸Dinic's Algorithm for Maximum Flow

🌊 Dinic's Algorithm for Maximum Flow

Explore how Dinic's algorithm speeds up maximum flow computation by alternating BFS-built level graphs with DFS-driven blocking flows, beating plain Edmonds-Karp on general graphs.

Algorithms & AI3DModerate60 FPS

The simulator visualizes both phases of Dinic's algorithm on a live flow network: a breadth-first search that labels every node with its shortest-path level and prunes the residual graph down to a level graph, followed by a depth-first blocking-flow search that pushes flow along multiple augmenting paths in one pass while skipping saturated edges via pointer bookkeeping, repeating until no augmenting path remains.

🔬 What It Demonstrates

🎮 How to Use

Step through the BFS phase to watch levels get assigned node by node and see which residual edges survive into the level graph. Then step through the DFS blocking-flow phase to watch paths get discovered, flow get pushed along the bottleneck edge, and pointers advance past saturated edges. Trigger a phase rebuild to see a fresh BFS run on the updated residual graph, and observe the source-to-sink distance increase with each new phase until the algorithm terminates.

💡 Did You Know?

Dinic's algorithm was published in 1970 by Israeli-Soviet computer scientist Yefim (Efim) Dinic, and on unit-capacity graphs, the same kind that arise in bipartite matching, it runs in O(E times square root of V) time, making it a foundational building block for later specialized matching algorithms.

⚙ Under the hood

Explore how Dinic's algorithm speeds up maximum flow computation by alternating BFS-built level graphs with DFS-driven blocking flows, beating plain Edmonds-Karp on general graphs.

graph theorymax flowalgorithmsnetwork flowdinicbfsdfscomplexity

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install