形式陈述

Dinic 算法在残量网络中用 BFS 计算从源的层次 $level$，只保留满足 $level[v]=level[u]+1$ 的层次边，随后用 DFS 找阻塞流：使层次图中每条 $s$-$t$ 路至少有一条边饱和。每个阶段后最短增广路长度严格增加，阶段数少于 $|V|$；一般容量网络时间 $O(|V{|}^2|E|)$。单位容量或二分图匹配有更好界。当前弧优化避免 DFS 反复扫描已证无用的边。

直觉

不是一次只找一条路，而是在同一最短层次上尽量把所有可送流一次送尽；当这一层被堵住，再重新 BFS 寻找更长路线。

例子与边界

BFS 层次图不包含同层或后退边，因而无环。阻塞流不一定是该层次图中的最大流，只需阻断所有源汇路。DFS 返回可推流量并更新正反残量；忘记反向边会失去正确性。若每次只增广一条而不求阻塞流，复杂度退化成其他方法。浮点容量可能引入数值比较问题，理论分析通常假设精确算术。

推论与应用

Dinic 是工程上常用的通用最大流算法，适合竞赛、匹配和中等规模网络，也是层次网络思想的代表。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。