迪尼茨演算法

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

歷史

迪尼茨在格奧爾吉·阿傑爾松-韋利斯基（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.

參見

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