迪尼茨算法

叶菲姆·迪尼茨在Adel'son-Vel'sky（AVL树的发明者之一）的算法课的课前活动上发明了这个算法。当时他不知道关于福特-富尔克森算法的基本事实。^[2]

迪尼茨在1969年一月向他人公布了他发明的算法，又在1970年将其发布在《Doklady Akademii nauk SSSR杂志》。在1974年，希蒙·埃文和（他之后的博士学生）Alon Itai在海法的以色列理工学院对迪尼茨的算法以及亚历山大·卡尔扎诺夫的阻塞流的想法很感兴趣。但是杂志上的文章每篇的篇幅被限制在四页以内，很多细节都被忽略，这导致他们很难根据文章还原出算法。但他们没有放弃，在后三天不断地努力，设法了解这两个文件中的分层网络的维护问题。在接下来的几年，Even由于在讲学中将Dinitz念为Dinic，导致Dinic算法反而成为了它的名称。埃文和Itai也将算法与BFS和DFS结合起来，形成了当前版本的算法。^[3]

在福特-富尔克森算法发明后约十年之内，是否有算法能在多项式复杂度之内处理无理数边权是未知的。这造成缺乏任何已知的多项式复杂度算法解决最大流问题。 迪尼茨算法和埃德蒙兹-卡普算法在1972年发布，证明在福特-富尔克森算法中，如果每次总选择最短的一条增广路，路径长度将单调增加，且算法总能终止。

设${\displaystyle G=((V,E),c,s,t)}$ 为一个每条边的容量为${\displaystyle c(u,v)}$ ，流为${\displaystyle f(u,v)}$ 的网络。

残留容量${\displaystyle c_{f}\colon V\times V\to R^{+}}$ 的定义为：

1. 如果${\displaystyle (u,v)\in E}$ ,

   ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$ 

   ${\displaystyle c_{f}(v,u)=f(u,v)}$ 

2. 否则${\displaystyle c_{f}(u,v)=0}$ 。

则残留网络为${\displaystyle G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)}$ ，其中

${\displaystyle E_{f}=\{(u,v)\in V\times V:c_{f}(u,v)>0\}}$ .

增广路指通过残留网络${\displaystyle G_{f}}$ 的从源点${\displaystyle s}$ 到汇点${\displaystyle t}$ 的一条有效路径。

定义${\displaystyle \operatorname {dist} (v)}$ 为${\displaystyle G_{f}}$ 中从源点${\displaystyle s}$ 到点${\displaystyle v}$ 的最短距离。那么${\displaystyle G_{f}}$ 的高度标号为${\displaystyle G_{L}=(V,E_{L},c_{f}|_{E_{L}},s,t)}$ ，其中

${\displaystyle E_{L}=\{(u,v)\in E_{f}:\operatorname {dist} (v)=\operatorname {dist} (u)+1\}}$ .

设图${\displaystyle G'=(V,E_{L}',s,t)}$ ，其中${\displaystyle E_{L}'=\{(u,v):f(u,v)<c_{f}|_{E_{L}}(u,v)\}}$ 不包含从${\displaystyle s}$ 到${\displaystyle t}$ 的路径，则阻塞流为一条从${\displaystyle s}$ 到${\displaystyle t}$ 的流${\displaystyle f}$ 。

迪尼茨算法

输入:网络${\displaystyle G=((V,E),c,s,t)}$ 。

输出:${\displaystyle s-t}$ 的流${\displaystyle f}$ 的最大值。

1. 对每条边${\displaystyle e\in E}$ ，设${\displaystyle f(e)=0}$ 。
2. 在图${\displaystyle G}$ 的残留网络${\displaystyle G_{f}}$ 中计算${\displaystyle G_{L}}$ 。如果${\displaystyle \operatorname {dist} (t)=\infty }$ 停止程序并输出${\displaystyle f}$ .
3. 在${\displaystyle G_{L}}$ 找到一条阻塞流${\displaystyle f\;'}$ 。
4. 将${\displaystyle \ f}$ 增加${\displaystyle f\;'}$ 并返回第二步。

可以证明每轮算法中找到的阻塞流的边数至少增加1，因此整个网络中最多有${\displaystyle n-1}$ 条阻塞流, ${\displaystyle n}$ 为网络中顶点的数量。高度标号${\displaystyle G_{L}}$ 可以在${\displaystyle O(E)}$ 的时间复杂度内用BFS构建，一条阻塞流可以在${\displaystyle O(VE)}$ 的复杂度内构建。因此，算法的时间复杂度为${\displaystyle O(V^{2}E)}$ .

使用一种叫做动态树的数据结构，找到阻塞流的时间复杂度可以降到${\displaystyle O(E\log V)}$ ，此时迪尼茨算法的复杂度可以降到${\displaystyle O(VE\log V)}$ .

特殊情况

在具有单位容量的网络中，迪尼茨算法可以在更短的时间内输出结果。每条阻塞流可以在${\displaystyle O(E)}$ 的时间内构建，并且阶段（phases）的数量不超过${\displaystyle O({\sqrt {E}})}$ 或${\displaystyle O(V^{2/3})}$ 。此时算法的复杂度为${\displaystyle O(\min\{V^{2/3},E^{1/2}\}E)}$ 。^[4]

在二分图匹配问题的网络中，阶段的数量不超过${\displaystyle O({\sqrt {V}})}$ ，算法的时间复杂度不超过${\displaystyle O({\sqrt {V}}E)}$ 。这种算法又叫霍普克罗夫特-卡普算法。同样的上界也适用于更一般情况，即unit网络——网络中除源点及汇点外的顶点，都仅有一条容量为1的外向边，或是仅有一条容量为1的内向边，并且所有的容量限制都是整数。^[5]

• Tarjan, R. E. Data structures and network algorithms. 1983. 

• 网络流
• 福特-富尔克森算法