迪尼茨演算法

迪尼茨演算法是佇網路流計算上大流的差多項式複雜度的演算法，設想由以色列電腦科學家葉菲姆・迪尼茨佇一九七空年提出。演算法 $ O ( V ^ { 二 } E ) $ 的時間複雜度類似佇埃德蒙茲-卡普演算法，其時間複雜度做 $ O ( VE ^ { 二 } ) $，迪尼茨演算法佮埃德蒙茲-卡普演算法的無仝的所在在在逐輪演算法攏選擇上短的會當行路徑來進行增廣。迪尼茨演算法中採用高度標號（level graph）以及阻塞流（blocking flow）實現效能。

歷史

葉菲姆・迪尼茨佇 Adel'son-Vel'sky（AVL 樹仔的發明者之一）的演算法課的課前活動上發明矣這个演算法。彼當陣伊毋知關於福特-富爾克森演算法的基本事實。

迪尼茨佇一九六九年一月共𪜶人公佈矣伊發明的演算法，閣佇一九七空年就欲發佈《Doklady Akademii nauk SSSR 雜誌》。佇咧一九七四年，希蒙・埃文佮（伊以後的博士學生）Alon Itai 佇海法的以色列理工學院對迪尼茨的演算法猶閣有亞歷山大・卡爾鑿諾夫的阻塞流的想法足感興趣的。猶毋過雜誌上的文章逐篇的篇幅予人限制佇咧四頁以內，足濟細節攏去予人無注意著，這致使𪜶真歹根據文章還原出演算法。但是𪜶無放棄，在後三日不斷會拍拚，設法了解這兩个檔案中的分層網路的維護問題。佇紲落來的幾年，Even 因為佇講學中將 Dinitz 唸做 Dinic，致使著 Dinic 演算法顛倒變做伊的名稱。埃文佮 Itai 嘛會演算法佮 BFS 和 DFS 敆起來，形成目前版本的演算法。

佇福特-富爾克森演算法發明了後差不多十年以內，敢有演算法會當佇多項式複雜度內底處理無理數邊權是未知的。這造成欠缺任何已知的多項式複雜度演算法解決上大流的問題。迪尼茨演算法佮埃德蒙茲-卡普演算法佇一九七二年發佈，證明佇福特-富爾克森演算法內底，若逐擺總選擇上短的一條增廣路，路徑長度共單調增加，而且演算法總能終止。

定義

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

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

一 . 若是 $ ( u , v ) \ in E $ ,

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

$ c _ { f } ( v , u )=f ( u , v ) $

二 . 抑無 $ c _ { f } ( u , v )=零 $。

著殘留網路為 $ G _ { f }=( ( V , E _ { f } ) , c _ { f } | _ { E _ { f } } , s , t ) $，其中

$ E _ { f }=\ { ( u , v ) \ in V \ times V : c _ { f } ( u , v ) > 零 \ } $ .

增廣路指通過殘留網路 $ 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 ) + 一 \ } $ .

設圖 $ 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 $ 的上大值。

一 . 著逐條邊 $ e \ in E $，設 $ f ( e )=零 $。二 . 咧圖 $ G $ 的殘留網路 $ G _ { f } $ 中計算 $ G _ { L } $。若是 $ \ operatorname { dist } ( t )=\ infty $ 停止程式並輸出 $ f $ . 三 . 佇咧 $ G _ { L } $ 揣著一條阻窒流 $ f \ ;'$。四 . 將 $ \ f $ 加添 $ f \ ;'$ 閣倒轉來第二步。

分析

會當證明逐輪演算法內底揣著的阻窒流的邊數至少增加一，因此規个網路中上濟有 $ n 影一 $ 條阻塞流，$ n $ 為網路中頂點的數量。懸度標號 $ G _ { L } $ 會當佇 $ O ( E ) $ 的時間複雜度內底用 BFS 構建，一條阻塞流會當佇咧 $ O ( VE ) $ 的複雜度內構建。所以，演算法的時間複雜度做 $ O ( V ^ { 二 } E ) $ .

使用一種叫做動態樹的資料結構，揣著阻塞流的時間複雜度會當降甲 $ O ( E \ log V ) $，這陣迪尼茨伊算法的複雜度會當降到 $ O ( VE \ log V ) $ .

特殊情況

佇咧具有單位容量的網路內底，迪尼茨彼个演算法會當佇閣較短的時間內輸出結果。逐條阻窒流會當佇咧 $ O ( E ) $ 的時間內構建，並且階段（phases）的數量無超過 $ O ( { \ sqrt { E } } ) $ 抑是 $ O ( V ^ { 三分之二 } ) $。現此時演算法的複雜度做 $ O ( \ min \ { V ^ { 三分之二 } , E ^ { 二分之一 } \ } E ) $。

佇第二分圖匹配的問題的網路內底，階段的數量無超過 $ O ( { \ sqrt { V } } ) $，演算法的時間複雜度無超過 $ O ( { \ sqrt { V } } E ) $。這種演算法閣叫霍普克羅夫特-卡普演算法。仝款的上界嘛會當用佇閣較一般的情形，即 unit 網路—— 網路中除源點佮匯點外口的頂點，攏干焦有一條容量為一的外向邊仔，抑是干焦一條容量做一个閉思邊，並且所有的容量限制攏是整數。

參考文獻

Tarjan , R . E . Data structures and network algorithms . 一千九百八十三 .

參見

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