Dinic 算法 | Codeboy's Blog

形式陈述

给定最大流问题的容量网络。对当前可行流 $f$ 的残量网络 $G_f$ ，Dinic 算法先用广度优先搜索计算

level[v]=\operatorname{dist}_{G_f}(s,v),

距离按正残量弧数计，不可达时为 $+\infty$ 。若 $t$ 不可达，算法停止。否则只保留满足

c_f(u,v)>0, \qquad level[v]=level[u]+1

的残量记录，得到层次图。层号沿每条保留弧严格增加，所以它是 DAG。

一个阶段在层次图中发送阻塞流：更新后，每条层次图的 $s$ – $t$ 路都至少含一条已饱和记录。标准实现从 $s$ 做受层号约束的深度优先搜索，递归返回可推送量，并为每个顶点保存 current[v]，指向尚未证伪的第一条出记录。某条边已无残量或其后继无法送到 $t$ 后，本阶段不再从头扫描它。

阻塞阶段后，残量最短路长度严格增加。BFS 性质保证旧残量图中任意弧最多让层号增加 $1$ ；本阶段新增的反向残量弧从第 $i+1$ 层指回第 $i$ 层。若新残量图仍有长度等于 $level[t]$ 的源汇路，它的每一步都必须恰好前进一层，从而是一条未被阻断的旧层次路，矛盾。因此阶段数至多 $|V|-1$ ；当 BFS 不能到达 $t$ 时，由最大流最小割定理得到最大流。

设 $n=|V|$ 、 $m=|A|$ ，残量记录数为 $O(m)$ 。邻接表和精确单位成本算术下，BFS 为 $O(n+m)$ 。一个阻塞流阶段中，当前弧使失败记录只前进一次；每次成功的源汇推送至少饱和一条尚未饱和的层次记录，至多 $O(m)$ 次，每条递归路长至多 $n-1$ ，故阶段时间 $O(nm)$ ，一般确定性最坏时间为

O(n^2m),

空间为 $O(n+m)$ 。若网络是匹配归约一类 unit network——所有容量为 $1$ ，且除 $s,t$ 外每个顶点至多只有一条入弧或至多只有一条出弧——可把界加强为 $O(m\sqrt n)$ ；仅有“容量全为 $1$ ”不足以套用这一界。

直觉

Ford–Fulkerson 一次只利用一条增广路，Dinic 则先固定当前最短残量距离，再把这一距离层中的所有源汇通道一起堵住。层次图禁止同层和后退移动，DFS 因而只处理一张无环的方向骨架；阻塞完成后，下一次增广必须使用更多弧。

阻塞流不必是层次图上的最大流。它只需让每条当前最短源汇路至少有一个瓶颈饱和，以便证明距离推进；额外求层次图最大流不在这项复杂度证明的要求之内。

Dinic 算法的 BFS 层次、层次图和阻塞流阶段演化 — Dinic：层次图与阻塞流

例子与边界

取容量

s\to a:2,\quad s\to b:1,\quad a\to c:1,\quad a\to d:1,\quad b\to d:1,\quad c\to t:1,\quad d\to t:2.

第一次 BFS 给 $a,b$ 层号 $1$ ， $c,d$ 层号 $2$ ， $t$ 层号 $3$ 。层次图包含三条可共同承载的单位路线： $s\to a\to c\to t$ 、 $s\to a\to d\to t$ 、 $s\to b\to d\to t$ ；阻塞流在这一阶段送出 $3$ ，源出边与汇入边也都达到容量，随后 BFS 不再到达 $t$ 。

若 DFS 沿不满足层号递增的残量边行走，或找到一条路便立刻重做 BFS，算法仍可能保持某种增广正确性，却失去“每阶段阻断全部最短路”的证明与 $O(n^2m)$ 界。忘记更新反向残量记录会阻止以后撤销；反平行原弧与反向记录还必须以边 ID 区分。

阶段数与容量数值无关，因此精确实容量下也有有限组合进度，不需要容量可积。浮点实现却必须规定零残量容差，并防止极小误差让理论上饱和的边长期保留；组合复杂度按精确比较与算术理解。

推论与应用

Dinic 在二分图匹配流网络上得到 unit-network 强化界；专门的Hopcroft–Karp 算法直接在交替图上表达相同“最短增广路分阶段”思想，省去显式源汇弧。普通容量分配仍使用本页的一般界，不能因容量恰为小整数就自动声称 $O(m\sqrt n)$ 。

Push–Relabel不构造完整层次图，而维护预流、超额与局部高度，按 active vertex 放电。两者都是与容量数值无关的多项式最大流算法，但进度量分别是残量源汇距离与高度/超额势函数。

带下界与需求的可行环流要先消去下界、计算节点不平衡并加入超级源汇，再把可行性归约成最大流；负“剩余容量”不属于 Dinic 的合法输入。

参考资料

E. A. Dinic, “Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation,” Soviet Mathematics Doklady 11, 1970, pp. 1277–1280。
Shimon Even and Robert E. Tarjan, “Network Flow and Testing Graph Connectivity,” SIAM Journal on Computing 4(4), 1975, pp. 507–518。
Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin, Network Flows, Prentice Hall, 1993。

形式陈述 ​

反向链接

形式陈述