福特-富爾克森演算法

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

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

## 演算法

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

容量限制:｜$\forall (u, v) \in E, f(u,v) \le c(u,v)$｜每條邊上的流都不能超出邊的最大流量。

反向對稱:｜$\forall (u, v) \in E, f(u,v) = - f(v,u)$｜從$u$到$v$的流量一定是從$v$到$u$的流量的相反數（見樣例）。

流量守恆:｜$\forall u \in V: u \neq s, u \neq t \Rightarrow \sum_{w \in V} f(u,w) = 0$｜除非$u$是源點$s$或匯點$t$，一個節點的淨流量為零。

f的值:｜$\sum_{(s,u) \in E} f(s, u) = \sum_{(v,t) \in E} f(v, t)$｜從源點$s$流出的流量一定等於匯點$t$接收的流量。

這意味著每輪計算之後通過網路的都是一個流。我們定義殘留網路 $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$。

- 初始化網路流量$f\leftarrow 0$、殘留網路$G_f \leftarrow G$。對於圖的每一條邊$(u,v)$，初始化流量$f(u,v) \leftarrow 0$。
- 只要$G_f$中還存在一條從$s$到$t$的路徑$p$，使對於每一條邊$(u,v) \in p$，都有$c_f(u,v) > 0$：
- 設置路徑$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)$ （這個流在之後可以被「發送」回來）

步驟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(E f)$（參見大O符號）, $E$圖中的邊數，$f$為最大流。這是因為一條增廣路徑可以在$O(E)$的時間複雜度內找到，每輪演算法執行後流量的增長至少為$1$。但是在極端情況下，演算法有可能永遠不會停止。

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

## 樣例

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

路徑｜容量｜網路

原流｜

<image>

$A,B,C,D$｜$\begin{align} & \min(c_f(A,B), c_f(B,C), c_f(C,D)) \\ = & \min(c(A,B)-f(A,B) ,c(B,C)-f(B,C), c(C,D)-f(C,D)) \\ = & \min(1000-0, 1-0, 1000-0) = 1 \end{align}$｜

<image>

$A,C,B,D$｜$\begin{align} & \min(c_f(A,C), c_f(C,B), c_f(B,D)) \\ = & \min(c(A,C)-f(A,C), c(C,B)-f(C,B), c(B,D)-f(B,D)) \\ = & \min(1000-0, 0-(-1), 1000-0) = 1 \end{align}$｜

<image>

1998輪之後…

最終流｜

<image>

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

## 無法終止演算法的樣例

<image>

右圖所示的網路中源點為$s$，匯點為$t$邊$e_1$、$e_2$、$e_3$的容量為$1$, $r=(\sqrt{5}-1)/2$和$1$，使$r^2 = 1 - r$。其它所有邊的容量$M \ge 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 \}$.

步驟｜增廣路徑｜發送流｜剩餘容量

$e_1$｜$e_2$｜$e_3$

0｜$r^0=1$｜$r$｜$1$

1｜$\{ s, v_2, v_3, t \}$｜$1$｜$r^0$｜$r^1$｜$0$

2｜$p_1$｜$r^1$｜$r^2$｜$0$｜$r^1$

3｜$p_2$｜$r^1$｜$r^2$｜$r^1$｜$0$

4｜$p_1$｜$r^2$｜$0$｜$r^3$｜$r^2$

5｜$p_3$｜$r^2$｜$r^2$｜$r^3$｜$0$

注意在步驟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源碼

```python
class Edge(object):
    def __init__(self, u, v, w):
        self.source = u
        self.sink = v  
        self.capacity = w
    def __repr__(self):
        return "%s->%s:%s" % (self.source, self.sink, self.capacity)

class FlowNetwork(object):
    def __init__(self):
        self.adj = {}
        self.flow = {}
 
    def add_vertex(self, vertex):
        self.adj[vertex] = []
 
    def get_edges(self, v):
        return self.adj[v]
 
    def add_edge(self, u, v, w=0):
        if u == v:
            raise ValueError("u == v")
        edge = Edge(u,v,w)
        redge = Edge(v,u,0)
        edge.redge = redge
        redge.redge = edge
        self.adj[u].append(edge)
        self.adj[v].append(redge)
        self.flow[edge] = 0
        self.flow[redge] = 0
 
    def find_path(self, source, sink, path):
        if source == sink:
            return path
        for edge in self.get_edges(source):
            residual = edge.capacity - self.flow[edge]
            if residual > 0 and edge not in path:
                result = self.find_path( edge.sink, sink, path + [edge]) 
                if result != None:
                    return result
 
    def max_flow(self, source, sink):
        path = self.find_path(source, sink, [])
        while path != None:
            residuals = [edge.capacity - self.flow[edge] for edge in path]
            flow = min(residuals)
            for edge in path:
                self.flow[edge] += flow
                self.flow[edge.redge] -= flow
            path = self.find_path(source, sink, [])
        return sum(self.flow[edge] for edge in self.get_edges(source))
```

### 使用樣例

```python
>>> g = FlowNetwork()
>>> [g.add_vertex(v) for v in "sopqrt"]
[None, None, None, None, None, None]
>>>
>>> g.add_edge('s','o',3)
>>> g.add_edge('s','p',3)
>>> g.add_edge('o','p',2)
>>> g.add_edge('o','q',3)
>>> g.add_edge('p','r',2)
>>> g.add_edge('r','t',3)
>>> g.add_edge('q','r',4)
>>> g.add_edge('q','t',2)
>>> print (g.max_flow('s','t'))
5
```

## 應用

二分圖的最大匹配

最大不相交路徑