迪尼茨算法

迪尼茨算法是在网络流计算最大流的强多项式复杂度的算法，设想由以色列计算机科学家叶菲姆·迪尼茨在1970年提出。^[1]算法${\displaystyle O(V^{2}E)}$的时间复杂度类似于埃德蒙兹-卡普算法，其时间复杂度为${\displaystyle O(VE^{2})}$，迪尼茨算法与埃德蒙兹-卡普算法的不同之处在于它每轮算法都选择最短的可行路径进行增广。迪尼茨算法中采用高度标号（level graph）以及阻塞流（blocking flow）实现性能。

历史

叶菲姆·迪尼茨在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]

参考文献

1. Yefim Dinitz. Algorithm for solution of a problem of maximum flow in a network with power estimation (PDF). Doklady Akademii nauk SSSR. 1970, 11: 1277–1280 [2016-08-04]. （原始内容 (PDF)于2016-08-22）. 
2. Ilan Kadar; Sivan Albagli. Dinitz's algorithm for finding a maximum flow in a network. 2009-11-27 [2016-08-04]. （原始内容于2016-06-24）. 
3. Yefim Dinitz. Dinitz's Algorithm: The Original Version and Even's Version (PDF). [2016-08-04]. （原始内容 (PDF)于2016-08-20）. 
4. Even, Shimon; Tarjan, R. Endre. Network Flow and Testing Graph Connectivity. SIAM Journal on Computing. 1975, 4 (4): 507–518. ISSN 0097-5397. doi:10.1137/0204043. 
5. Tarjan 1983，第102頁.

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

参见

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