福特-富尔克森算法

**福特 - 富爾克森方法**（英語：Ford–Fulkerson method），又稱**福特 - 富爾克森算法**（Ford–Fulkerson algorithm），是一類計算網絡流的最大流的貪心算法。之所以稱之為「方法」而不是「算法」，是因為它尋找增廣路徑的方式並不是完全確定的，而是有幾種不同時間複雜度的實現方式。它在 1956 年由小萊斯特・倫道夫・福特及德爾伯特・雷・富爾克森發表。「福特 - 富爾克森」這個名詞通常也指代埃德蒙茲 - 卡普算法，這是一個特殊的福特 - 富爾克森算法實現。

算法的思想如下：只要有一條從源點（開始節點）到匯點（結束節點）的路徑，在路徑的所有邊上都有可用容量，就沿著這條路徑發送一個流，流量由路徑上的最小容量限制。 然後再找到另一條路徑，一直到網絡中不存在這種路徑為止。 一條有可用容量的路徑被稱為一條增廣路徑。

## 算法

設 $G(V,E)$ 為一個圖，並且為每條從 $u$ 到 $v$ 的邊 $(u,v)$ 設置一個最大流量 $c(u,v)$ ，並且初始化當前流量 $f(u,v)=0$ 。下面是該算法每一步的實現：

　
:

這意味著每輪計算之後通過網絡的都是一個流。我們定義**殘留網絡** $G_{f}(V,E_{f})$ 是一個網絡的剩餘流量 $c_{f}(u,v)=c(u,v)-f(u,v)$ 。注意殘留網絡可以設置從 $v$ 到 $u$ 的流量，即使在原先的網絡中不允許這種情況產生：如果 $c(v,u)=0$ 但 $f(u,v)>0$ ，那麼 $c_{f}(v,u)=c(v,u)-f(v,u)=f(u,v)>0$ ：也即，從 $u$ 到 $v$ 的流量給從 $v$ 到 $u$ 的流量提供了額外的剩餘量。

### 偽代碼

**算法** 福特 - 富爾克森

　
: **輸入** 給定一張邊的容量為 $c$ 的圖 $G=(V,E)$ ，源點 $s$ 以及匯點 $t$ 。

　
: **輸出** 在網絡 $G$ 中，從 $s$ 到 $t$ 的最大流 $f$ 。

1. 初始化網絡流量 $f\leftarrow 0$ 、殘留網絡 $G_{f}\leftarrow G$ 。對於圖的每一條邊 $(u,v)$ ，初始化流量 $f(u,v)\leftarrow 0$ 。
2. 只要 $G_{f}$ 中還存在一條從 $s$ 到 $t$ 的路徑 $p$ ，使對於每一條邊 $(u,v)\in p$ ，都有 $c_{f}(u,v)>0$ ：
  1. 設置路徑 $p$ 本次應發送的流量為路徑最小剩餘流量： $c_{f}(p)\leftarrow \min _{(u,v)\in p}c_{f}(u,v)$ 。
  2. 更新網絡流量 $f\leftarrow f+c_{f}(p)$ 。
  3. 對於每一條邊 $(u,v)\in p$ ，更新 $G_{f}$ 的剩餘流量：
     1. $f(u,v)\leftarrow f(u,v)+c_{f}(p)$ （_在路徑中「發送」流）_
    2. $f(v,u)\leftarrow f(v,u)-c_{f}(p)$ （_這個流在之後可以被「發送」回來）_

步驟 2 中的路徑 $p$ 可以用廣度優先搜索或深度優先搜索在 $G_{f}(V,E_{f})$ 中找到。如果使用了廣度優先搜索，這個算法就是 Edmonds–Karp 算法。

當步驟 2 中找不到可行路徑時， $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)$ 的時間複雜度內找到，每輪算法執行後流量的增長至少為 $1$ 。但是在極端情況下，算法有可能永遠不會停止。

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

## 樣例

下面的樣例演示了福特 - 富爾克森在一張有 4 個節點，源點為 $A$ ，匯點為 $D$ 的圖中的第一輪計算。 這個例子顯示了算法在最壞情況下的行為。在每一輪算法中，只有 $1$ 的流量被發送至網絡中。如果算法改用寬度優先搜索，那麼只需要兩輪計算。

注意當找到路徑 $A,C,B,D$ 時，流是如何從 $C$ 發送至 $B$ 的。

## 無法終止算法的樣例

右圖所示的網絡中源點為 $s$ ，匯點為 $t$ 邊 $e_{1}$ 、 $e_{2}$ 、 $e_{3}$ 的容量為 $1$ , $r=({\sqrt {5}}-1)/2$ 和 $1$ ，使 $r^{2}=1-r$ 。其它所有邊的容量 $M\geq 2$ 。 使用福特 - 富爾克森算法可找到三條增廣路徑，分別為 $p_{1}=\{s,v_{4},v_{3},v_{2},v_{1},t\}$ 、 $p_{2}=\{s,v_{2},v_{3},v_{4},t\}$ 、 $p_{3}=\{s,v_{1},v_{2},v_{3},t\}$ .

注意在步驟 1 和步驟 5 之後，邊 $e_{1}$ 、 $e_{2}$ 、 $e_{3}$ 的殘留容量都可以表示為 $r^{n}$ 、 $r^{n+1}$ 或 $0$ ，同時，對於一些特殊的 $n\in \mathbb {N} $ 這意味著算法可以通過 $p_{1}$ 、 $p_{2}$ 、 $p_{1}$ 與 $p_{3}$ 無限增廣，並且殘留容量總處於一個循環。在步驟 5 之後網絡的流為 $1+2(r^{1}+r^{2})$ ，如果繼續用以上的算法增廣，總的流將向 $\textstyle 1+2\sum _{i=1}^{\infty }r^{i}=3+2r$ 趨近，但最大流為 $2M+1$ 。在這個樣例中，算法將永遠不會停止，且結果也不會向實際的最大流趨近。

## Python 源碼

### 使用樣例

## 應用

二分圖的最大匹配

最大不相交路徑

## 參考文獻

* Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Section 26.2: The Ford–Fulkerson method. Introduction to Algorithms Second. MIT Press and McGraw–Hill. 2001: 651–664. ISBN 0-262-03293-7.
* George T. Heineman; Gary Pollice; Stanley Selkow. Chapter 8:Network Flow Algorithms. Algorithms in a Nutshell. Oreilly Media. 2008: 226–250. ISBN 978-0-596-51624-6.
* Jon Kleinberg; Éva Tardos. Chapter 7:Extensions to the Maximum-Flow Problem. Algorithm Design. Pearson Education. 2006: 378–384. ISBN 0-321-29535-8.