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.
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.
Controls include stepping or auto-playing the BFS level-assignment phase, stepping or auto-playing the DFS blocking-flow phase, manually triggering a level-graph rebuild, adjusting graph size and edge capacities, resetting the flow to zero, and toggling display of residual capacities, current-edge pointers, and node levels.
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.
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.
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.
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.
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.