福特-富爾克森算法

福特-富爾克森方法（英語：Ford–Fulkerson method）， 閣稱福特-富爾克森算法（Ford–Fulkerson algorithm）， 是一類計算網路捷流的上大流的貪心算法。之所以講號做「方法」毋是「算法」，是因為伊走揣增廣路徑的方式並毋是完全確定的，是有幾種無仝時間複雜度的實現方式。伊佇一九五六年由小萊斯特 ・ 倫道夫 ・ 福特佮德爾伯特 ・ 雷 ・ 富爾克森發表。「福特-富爾克森」這个名詞通常嘛指代埃德蒙茲-卡普算法，這是一个特殊的福特-富爾克森算法實現。

算法的思想如下：只要有一條對源點（開始節點）到匯點（煞點）的路徑，咧路徑的所有那上攏有通用容量，就沿這條路徑發送一个流，流量是由路徑上細容量的限制。才閣揣著另外一條路徑，一直去網路內底無存在這種路徑為止。一條有通用容量的路徑予人號做一條增廣路徑。

算法

設 $ G ( V , E ) $ 為一个圖，並且為逐條對 $ u $ 到 $ v $ 的邊仔 $ ( u , v ) $ 設一个上大的流量 $ c ( u , v ) $，而且初初化當前流量 $ f ( u , v )=零 $。下跤是該算法每一步的實現：

這意味著逐輪計算了後通過網路的攏是一个流。咱定義殘留網路$ G _ { f } ( V , E _ { f } ) $ 是一个網路的賰的流量 $ c _ { f } ( u , v )=c ( u , v )-f ( u , v ) $。注意殘留網路會當設置對 $ v $ 到 $ u $ 的流量，就算佇原本的網路內底無允准這款情形產生：若是 $ c ( v , u )=零 $ 猶毋過 $ f ( u , v ) > 零 $，遐爾 $ c _ { f } ( v , u )=c ( v , u )-f ( v , u )=f ( u , v ) > 零 $：嘛即，對 $ u $ 到 $ v $ 的流量予對 $ v $ 到 $ u $ 的流量提供額外的賰的量。

偽代碼

算法福特-富爾克森

輸入予定一个邊的容量為 $ c $ 的圖 $ G=( V , E ) $，源點 $ s $ 猶閣有匯點 $ t $。

輸出咧網路 $ G $ 中，對 $ s $ 到 $ t $ 的上大流 $ f $。

一 . 初始化網路流量 $ f \ leftarrow 零 $、殘留網路 $ G _ { f } \ leftarrow G $。對圖的每一條邊 $ ( u , v ) $，初初化彼个流量 $ f ( u , v ) \ leftarrow 零 $。 二 . 只要 $ G _ { f } $ 中猶閣存在一條中間 $ s $ 到 $ t $ 的路徑 $ p $，予對每一條邊 $ ( u , v ) \ in p $，攏有 $ c _ { f } ( u , v ) > 零 $： 一 . 設置路徑 $ p $ 本擺應該發送的流量做路草上細賰的流量：$ c _ { f } ( p ) \ leftarrow \ min _ { ( u , v ) \ in p } c _ { f } ( u , v ) $。 二 . 更新網路佮電腦 $ f \ leftarrow f + c _ { f } ( p ) $。 三 . 對每一條邊 $ ( u , v ) \ in p $，更新 $ G _ { f } $ 賰落水的量： 一 . $ f ( u , v ) \ leftarrow f ( u , v ) + c _ { f } ( p ) $（_ 佇路徑中「發送」流）_ 二 . $ f ( v , u ) \ leftarrow f ( v , u )-c _ { f } ( p ) $（_ 這流佇咧以後會當予「發送」轉來）_

嘿步驟二中的路草 $ p $ 通用廣度優先搜查或者是深度優先搜查佇 $ G _ { f } ( V , E _ { f } ) $ 中揣著。若使用廣度優先搜查，這个算法就是 Edmonds–Karp 算法。

做步驟二中揣無會著行路草的時，$ s $ 就無法度通佇咧殘留網路內底到位 $ t $。設 $ S $ 伊是佇殘留網路內底 $ s $ 會當到達的節點的集合，然後對 $ S $ 到 $ V $ 的其餘部份的網路一方面等於咱揣著的對 $ s $ 到 $ t $ 所有流的總的流量，另外一方面所有按呢的流量組成做一个上限。這个說明阮揣著的流是上大的。參見上大流上細割定理。

你若圖 $ G ( V , E ) $ 有幾个源點佮匯點，會當揤落去下跤法處理：設 $ T=\ { t | t { \ text { 抹著肉 } } \ } $，$ S=\ { s | s { \ text { 鋪排 } } \ } $。加一个新的源點 $ s ^ { * } $ 佮所有源點有一條邊仔 $ ( s ^ { * } , s ) $ 相連，容量 $ c ( s ^ { * } , s )=d _ { s } \ ; ( d _ { s }=\ sum _ { ( s , u ) \ in E } c ( s , u ) ) $。添加一个新匯點 $ t ^ { * } $ 佮所有匯點 $ ( t , t ^ { * } ) $ 有一條邊相連，容量 $ c ( t , t ^ { * } )=d _ { t } \ ; ( d _ { t }=\ sum _ { ( v , t ) \ in E } c ( v , t ) ) $。然後執行福特-富爾克森算法。

按呢仝款，若較節咧 $ u $ 有通過限制 $ d _ { u } $，會當共這个點用兩个點 $ u _ { in } , u _ { out } $ 替換，用一條邊 $ ( u _ { in } , u _ { out } ) $ 相連，容量為 $ c ( u _ { in } , u _ { out } )=d _ { u } $。然後執行福特-富爾克森算法。

複雜度

算法通過添加揣著的增廣路徑的流量增加總流量，當無法度揣著增廣路徑的時陣，總流量就達到矣上大。當當流量是整數時，福特-富爾克森算法的運行時間為 $ O ( Ef ) $（參見大 O 符號）, $ E $ 圖當中的邊數，$ f $ 為上大流。這是因為一條增廣路徑會當佇 $ O ( E ) $ 的時間複雜度內底揣著，逐輪算法執行了後流量的增長至少為 $ 一 $。但是佇極端的狀況之下，算法有可能永遠袂停止。

福特-富爾克森算法的一个特例是埃德蒙茲-卡普算法，時間複雜度做 $ O ( VE ^ { 二 } ) $。

看仿

下跤的樣例演示福特-富爾克森佇一塊有四个節點，源點為 $ A $，匯點為 $ D $ 的圖內底的第一輪計算。這个例顯示矣算法佇上歹的情況下的行為。佇每一輪算法內底，只有 $ 一 $ 的流量予人發送去網路內底。算法改用闊度優先搜查，遐爾仔只要兩輪計算。

注意當揣著路草 $ A , C , B , D $ 時，流是按怎對 $ C $ 發送到 $ B $ 的。

無法度終止算法的款例

正圖所示的網路中源點為 $ s $，匯點為 $ t $ 邊 $ e _ { 一 } $、$ e _ { 二 } $、$ e _ { 三 } $ 彼个容量為 $ 一 $ , $ r=( { \ sqrt { 五 } } 影一 ) / 二 $ 和 $ 一 $，使 $ r ^ { 二 }=一-r $。其他所有邊仔的容量 $ M \ geq 二 $。使用福特-富爾克森算法會當揣著三條增廣路徑，分別為 $ p _ { 一 }=\ { s , v _ { 四 } , v _ { 三 } , v _ { 二 } , v _ { 一 } , t \ } $、$ p _ { 二 }=\ { s , v _ { 二 } , v _ { 三 } , v _ { 四 } , t \ } $、$ p _ { 三 }=\ { s , v _ { 一 } , v _ { 二 } , v _ { 三 } , t \ } $ .

注意佇咧步數一佮步數五了後，邊 $ e _ { 一 } $、$ e _ { 二 } $、$ e _ { 三 } $ 的殘留容量攏會當表示為 $ r ^ { n } $、$ r ^ { n + 一 } $ 抑是 $ 零 $，同時，去對一寡特殊的 $ n \ in \ mathbb { N } $ 這意味著算法會當過 $ p _ { 一 } $、$ p _ { 二 } $、$ p _ { 一 } $ 佮 $ p _ { 三 } $ 無限增廣，並且殘留容量總處佇一个循環。佇咧行五了後彼个網路的流為 $ 一 + 二 ( r ^ { 一 } + r ^ { 二 } ) $，若是繼續用以上的算法來增廣，總的流將向 $ \ textstyle 一 + 二 \ sum _ { i=一 } ^ { \ infty } r ^ { i }=三 + 二 r $ 趨近，猶毋過上大流為 $ 二 M + 一 $。佇這个樣例中，算法將永遠袂煞，而且結果嘛袂向實際的上大流趨近。

應用

強欲二分圖的上大匹配上大的無相交路徑

參考文獻

• Cormen , Thomas H . ; Leiserson , Charles E . ; Rivest , Ronald L . ; Stein , Clifford . Section 二十六孵二 : The Ford–Fulkerson method . Introduction to Algorithms Second . MIT Press and McGraw–Hill . 兩千空一 : 六仔五十一–六百六十四 . ISBN  空九二百六十二鋪三千二百九十三鋪七 .
• George T . Heineman ; Gary Pollice ; Stanley Selkow . Chapter 八 : Network Flow Algorithms . Algorithms in a Nutshell . Oreilly Media . 兩千空八 : 兩百二十六–兩百五十 . ISBN  九百七十八追空抹五百九十六知五一千六百二十四含六 .
• Jon Kleinberg ; Éva Tardos . Chapter 七 : Extensions to the Maximum-Flow Problem . Algorithm Design . Pearson Education . 二千空六 : 三百七十八–三百八十四 . ISBN  空九三百二十一鋪二二七九千五百三十五鋪八 .