Dinics

Dinic's algorithm, named after Yefim Dinic, is a widely used method for computing the maximum flow in a flow network. It operates by repeatedly constructing a level graph of the residual network with a breadth-first search and then finding a blocking flow within that level graph using depth-first search. This two-phase approach—level graph construction followed by blocking flow augmentation—continues until no s-t path remains in the residual graph, at which point the current flow is maximum.

The level graph assigns to each vertex a distance from the source along edges with positive residual capacity. In this restricted graph, the algorithm pushes flow along shortest augmenting paths from the source to the sink. The DFS uses a current-arc optimization to avoid revisiting exhausted edges, progressing until all possible augmentations within the current level graph are exhausted. When no more augmenting flow can be sent in the level graph, a new BFS can re-create the level structure, and the process repeats.

Dinic's algorithm yields a maximum s-t flow, and from the residual graph, the minimum cut can be obtained by the set of vertices reachable from the source. It is implemented with data structures such as adjacency lists and residual capacities.

Complexity-wise, the algorithm runs in general graphs in O(E V^2) time, with improvements for special cases (for example, unit capacities can achieve faster bounds). It is appreciated for its practical performance and simplicity, making it a standard choice in both theoretical and applied network flow problems.

Applications span from network design and scheduling to bipartite matching and various reductions to maximum flow problems. It is frequently included in standard algorithm libraries and used in competitive programming.