迪尼茨算法

迪尼茨算法（英語：Dinic's algorithm）是在網絡流計算最大流的強多項式複雜度的算法，設想由以色列計算機科學家葉菲姆·迪尼茨在1970年提出。算法$O(V^{2}E)$的時間複雜度類似於埃德蒙茲-卡普算法，其時間複雜度為$O(VE^{2})$，迪尼茨算法與埃德蒙茲-卡普算法的不同之處在於它每輪算法都選擇最短的可行路徑進行增廣。迪尼茨算法中採用高度標號（level graph）以及阻塞流（blocking flow）實現性能。

歷史

迪尼茨在格奧爾吉·阿傑爾松-韋利斯基（AVL樹的發明者之一）的算法課的課前活動上發明了這個算法。當時他不知道關於福特-富爾克森算法的基本事實。

迪尼茨在1969年一月向他人公布了他發明的算法，又在1970年將其發布在《Doklady Akademii nauk SSSR雜誌》。在1974年，希蒙·埃文和（他之後的博士學生）Alon Itai在海法的以色列理工學院對迪尼茨的算法以及亞歷山大·卡爾扎諾夫的阻塞流的想法很感興趣。但是雜誌上的文章每篇的篇幅被限制在四頁以內，很多細節都被忽略，這導致他們很難根據文章還原出算法。但他們沒有放棄，在後三天不斷地努力，設法了解這兩個文件中的分層網絡的維護問題。在接下來的幾年，Even由於在講學中將Dinitz念為Dinic，導致Dinic算法反而成為了它的名稱。埃文和Itai也將算法與BFS和DFS結合起來，形成了當前版本的算法。

在福特-富爾克森算法發明後約十年之內，是否有算法能在多項式複雜度之內處理無理數邊權是未知的。這造成缺乏任何已知的多項式複雜度算法解決最大流問題。 迪尼茨算法和埃德蒙茲-卡普算法在1972年發布，證明在福特-富爾克森算法中，如果每次總選擇最短的一條增廣路，路徑長度將單調增加，且算法總能終止。

定義

設$G=((V,E),c,s,t)$為一個每條邊的容量為$c(u,v)$，流為$f(u,v)$的網絡。

殘留容量$c_{f}\colon V\times V\to R^{+}$的定義為：

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

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

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

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

則殘留網絡為$G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)$，其中

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

增廣路指通過殘留網絡$G_{f}$的從源點$s$到匯點$t$的一條有效路徑。

定義$\operatorname {dist} (v)$為$G_{f}$中從源點$s$到點$v$的最短距離。那麼$G_{f}$的高度標號為$G_{L}=(V,E_{L},c_{f}|_{E_{L}},s,t)$，其中

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

設圖$G'=(V,E_{L}',s,t)$，其中$E_{L}'=\{(u,v):f(u,v)<c_{f}|_{E_{L}}(u,v)\}$不包含從$s$到$t$的路徑，則阻塞流為一條從$s$到$t$的流$f$。

算法

迪尼茨算法

輸入:網絡$G=((V,E),c,s,t)$。

輸出:$s-t$的流$f$的最大值。

1. 對每條邊$e\in E$，設$f(e)=0$。
2. 在圖$G$的殘留網絡$G_{f}$中計算$G_{L}$。如果$\operatorname {dist} (t)=\infty$停止程序並輸出$f$.
3. 在$G_{L}$找到一條阻塞流$f\;'$。
4. 將$\ f$增加$f\;'$並返回第二步。

分析

可以證明每輪算法中找到的阻塞流的邊數至少增加1，因此整個網絡中最多有$n-1$條阻塞流, $n$為網絡中頂點的數量。高度標號$G_{L}$可以在$O(E)$的時間複雜度內用BFS構建，一條阻塞流可以在$O(VE)$的複雜度內構建。因此，算法的時間複雜度為$O(V^{2}E)$.

使用一種叫做動態樹的數據結構，找到阻塞流的時間複雜度可以降到$O(E\log V)$，此時迪尼茨算法的複雜度可以降到$O(VE\log V)$.

特殊情況

在具有單位容量的網絡中，迪尼茨算法可以在更短的時間內輸出結果。每條阻塞流可以在$O(E)$的時間內構建，並且階段（phases）的數量不超過$O({\sqrt {E}})$或$O(V^{2/3})$。此時算法的複雜度為$O(\min\{V^{2/3},E^{1/2}\}E)$。

在二分圖匹配問題的網絡中，階段的數量不超過$O({\sqrt {V}})$，算法的時間複雜度不超過$O({\sqrt {V}}E)$。這種算法又叫霍普克羅夫特-卡普算法。同樣的上界也適用於更一般情況，即unit網絡——網絡中除源點及匯點外的頂點，都僅有一條容量為1的外向邊，或是僅有一條容量為1的內向邊，並且所有的容量限制都是整數。

參考文獻

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

參見

• 網絡流
• 福特-富爾克森算法