Dinic's algorithm solves a maximum flow problem by repeatedly constructing the level graph of the residual network using breadth-first search, then sending a blocking flow through edges advancing one level. A blocking flow saturates at least one edge on every source-to-sink path in this level graph.
After a phase, no shortest residual path from the previous phase remains; the residual distance to the sink strictly increases if it remains reachable. Hence there are fewer than successful phases. With current-edge pointers and a standard blocking-flow implementation, the general bound is . When the sink becomes unreachable, the reachable vertices define a minimum cut, certifying the maximum flow. Residual reverse edges must be maintained so later phases can undo earlier choices.
Articles by others on the same topic
Dinic's algorithm, also known as Dinitz's algorithm, is an efficient method for solving the maximum flow problem in flow networks. It was proposed by the Israeli computer scientist Yefim Dinitz in 1970. The algorithm works on directed graphs and is particularly notable for its ability to handle large networks effectively. ### Key Concepts 1.