Dinic 算法

定义

Dinic 算法(又译 Dinitz 算法)由苏联计算机科学家 Yefim Dinitz 于 1970 年提出,是求网络最大流的高效算法,理论复杂度 O(V²E),实际表现通常远好于上界。

原理

算法分阶段运行:每阶段先在残量网络上做 BFS,按到源点的距离给顶点分层,只保留由低层指向高层的边构成分层图;然后用 DFS 在分层图中反复寻找增广路径直至找不到,即求出一个阻塞流。当前弧优化记录每个顶点已检查到的出边,避免重复扫描。由于每阶段源汇距离至少加一,阶段数不超过 V-1。

特殊性质

在所有边容量为 1 的图上复杂度降为 O(E√E) 级别;跑二分图匹配时等价于 Hopcroft-Karp,复杂度 O(E√V)。

应用

最大流、最小割、二分图匹配、项目选择与图像分割等归约到网络流的问题,是算法竞赛中最常用的最大流实现。