= Dinic's algorithm
{c}
= Dinic algorithm
{c}
{synonym}
= Dinic
{c}
{synonym}
<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 $V$ successful phases. With current-edge pointers and a standard blocking-flow implementation, the general bound is $O(V^2E)$. 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.
Back to article page
