福特-富尔克森算法

福特-富尔克森方法（英語：Ford–Fulkerson method），又稱福特-富尔克森算法（Ford–Fulkerson algorithm），是一类计算网络流的最大流的贪心算法。之所以称之为“方法”而不是“算法”，是因为它寻找增广路径的方式并不是完全确定的，而是有几种不同时间复杂度的实现方式^[1][2]。它在1956年由小萊斯特·倫道夫·福特及德爾伯特·雷·富爾克森^[3]发表。“福特-富尔克森”这个名词通常也指代埃德蒙兹-卡普算法，这是一个特殊的福特-富尔克森算法实现。

算法的思想如下：只要有一条从源点（开始节点）到汇点（结束节点）的路径，在路径的所有边上都有可用容量，就沿着这条路径发送一个流，流量由路径上的最小容量限制。 然后再找到另一条路径，一直到网络中不存在这种路径为止。 一条有可用容量的路径被称为一条增广路径。

算法

设${\displaystyle G(V,E)}$ 为一个图，并且为每条从${\displaystyle u}$ 到${\displaystyle v}$ 的边${\displaystyle (u,v)}$ 设置一个最大流量${\displaystyle c(u,v)}$ ，并且初始化当前流量${\displaystyle f(u,v)=0}$ 。下面是该算法每一步的实现：

容量限制:	${\displaystyle \forall (u,v)\in E,f(u,v)\leq c(u,v)}$	每条边上的流都不能超出边的最大流量。
反向对称:	${\displaystyle \forall (u,v)\in E,f(u,v)=-f(v,u)}$	从${\displaystyle u}$ 到${\displaystyle v}$ 的流量一定是从${\displaystyle v}$ 到${\displaystyle u}$ 的流量的相反数（见样例）。
流量守恒:	${\displaystyle \forall u\in V:u\neq s,u\neq t\Rightarrow \sum _{w\in V}f(u,w)=0}$	除非${\displaystyle u}$ 是源点${\displaystyle s}$ 或汇点${\displaystyle t}$ ，一个节点的净流量为零。
f的值:	${\displaystyle \sum _{(s,u)\in E}f(s,u)=\sum _{(v,t)\in E}f(v,t)}$	从源点${\displaystyle s}$ 流出的流量一定等于汇点${\displaystyle t}$ 接收的流量。

这意味着每轮计算之后通过网络的都是一个流。我们定义残留网络 ${\displaystyle G_{f}(V,E_{f})}$ 是一个网络的剩余流量${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$ 。注意残留网络可以设置从${\displaystyle v}$ 到${\displaystyle u}$ 的流量，即使在原先的网络中不允许这种情况产生：如果 ${\displaystyle c(v,u)=0}$  但 ${\displaystyle f(u,v)>0}$ ，那么${\displaystyle c_{f}(v,u)=c(v,u)-f(v,u)=f(u,v)>0}$ ：也即，从${\displaystyle u}$ 到${\displaystyle v}$ 的流量给从${\displaystyle v}$ 到${\displaystyle u}$ 的流量提供了额外的剩余量。

伪代码

算法 福特-富尔克森

输入 给定一张边的容量为${\displaystyle c}$ 的图${\displaystyle G=(V,E)}$ ，源点${\displaystyle s}$ 以及汇点${\displaystyle t}$ 。

输出 在网络${\displaystyle G}$ 中，从${\displaystyle s}$ 到${\displaystyle t}$ 的最大流${\displaystyle f}$ 。

1. 初始化网络流量${\displaystyle f\leftarrow 0}$ 、残留网络${\displaystyle G_{f}\leftarrow G}$ 。对于图的每一条边${\displaystyle (u,v)}$ ，初始化流量${\displaystyle f(u,v)\leftarrow 0}$ 。
2. 只要${\displaystyle G_{f}}$ 中还存在一条从${\displaystyle s}$ 到${\displaystyle t}$ 的路径${\displaystyle p}$ ，使对于每一条边${\displaystyle (u,v)\in p}$ ，都有${\displaystyle c_{f}(u,v)>0}$ ：
   1. 设置路径${\displaystyle p}$ 本次应发送的流量为路径最小剩余流量：${\displaystyle c_{f}(p)\leftarrow \min _{(u,v)\in p}c_{f}(u,v)}$ 。
   2. 更新网络流量${\displaystyle f\leftarrow f+c_{f}(p)}$ 。
   3. 对于每一条边${\displaystyle (u,v)\in p}$ ，更新${\displaystyle G_{f}}$ 的剩余流量：
      1. ${\displaystyle f(u,v)\leftarrow f(u,v)+c_{f}(p)}$  （在路径中“发送”流）
      2. ${\displaystyle f(v,u)\leftarrow f(v,u)-c_{f}(p)}$  （这个流在之后可以被“发送”回来）

步骤2中的路径${\displaystyle p}$ 可以用广度优先搜索或深度优先搜索在${\displaystyle G_{f}(V,E_{f})}$ 中找到。如果使用了广度优先搜索，这个算法就是Edmonds–Karp算法。

当步骤2中找不到可行路径时，${\displaystyle s}$ 就无法在残留网络中到达${\displaystyle t}$ 。设${\displaystyle S}$ 是在残留网络中${\displaystyle s}$ 可以到达的节点的集合，然后从${\displaystyle S}$ 到${\displaystyle V}$ 的其余部分的网络一方面等于我们找到的从${\displaystyle s}$ 到${\displaystyle t}$ 的所有流的总流量，另一方面所有这样的流量组成了一个上限。这说明我们找到的流是最大的。参见最大流最小割定理。

如果图${\displaystyle G(V,E)}$ 有多个源点和汇点，可以按如下方法处理：设${\displaystyle T=\{t|t{\text{为 目 标 点 }}\}}$ ，${\displaystyle S=\{s|s{\text{为 源 点 }}\}}$ 。 添加一个新源点${\displaystyle s^{*}}$ 与所有源点有一条边${\displaystyle (s^{*},s)}$ 相连，容量${\displaystyle c(s^{*},s)=d_{s}\;(d_{s}=\sum _{(s,u)\in E}c(s,u))}$ 。添加一个新汇点${\displaystyle t^{*}}$ 与所有汇点${\displaystyle (t,t^{*})}$  有一条边相连，容量${\displaystyle c(t,t^{*})=d_{t}\;(d_{t}=\sum _{(v,t)\in E}c(v,t))}$ 。然后执行福特-富尔克森算法。

同样的，如果节点${\displaystyle u}$ 有通过限制${\displaystyle d_{u}}$ ，可将这个节点用两个节点${\displaystyle u_{in},u_{out}}$ 替换，用一条边${\displaystyle (u_{in},u_{out})}$ 相连，容量为${\displaystyle c(u_{in},u_{out})=d_{u}}$ 。然后执行福特-富尔克森算法。

复杂度

算法通过添加找到的增广路径的流量增加总流量，当无法找到增广路径时，总流量就达到了最大。当流量是整数时，福特-富尔克森算法的运行时间为${\displaystyle O(Ef)}$ （参见大O符号）, ${\displaystyle E}$ 图中的边数，${\displaystyle f}$ 为最大流。 这是因为一条增广路径可以在${\displaystyle O(E)}$ 的时间复杂度内找到，每轮算法执行后流量的增长至少为${\displaystyle 1}$ 。但是在极端情况下，算法有可能永远不会停止。

福特-富尔克森算法的一个特例是埃德蒙兹-卡普算法，时间复杂度为${\displaystyle O(VE^{2})}$ 。

样例

下面的样例演示了福特-富尔克森在一张有4个节点，源点为${\displaystyle A}$ ，汇点为${\displaystyle D}$ 的图中的第一轮计算。 这个例子显示了算法在最坏情况下的行为。在每一轮算法中，只有${\displaystyle 1}$ 的流量被发送至网络中。如果算法改用宽度优先搜索，那么只需要两轮计算。

路径	容量	网络
原流
${\displaystyle A,B,C,D}$	${\displaystyle {\begin{aligned}&\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{aligned}}}$
${\displaystyle A,C,B,D}$	${\displaystyle {\begin{aligned}&\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{aligned}}}$
1998轮之后…
最终流

注意当找到路径${\displaystyle A,C,B,D}$ 时，流是如何从${\displaystyle C}$ 发送至${\displaystyle B}$ 的。

无法终止算法的样例

 

右图所示的网络中源点为${\displaystyle s}$ ，汇点为${\displaystyle t}$ 边${\displaystyle e_{1}}$ 、${\displaystyle e_{2}}$ 、${\displaystyle e_{3}}$ 的容量为${\displaystyle 1}$ , ${\displaystyle r=({\sqrt {5}}-1)/2}$ 和${\displaystyle 1}$ ，使${\displaystyle r^{2}=1-r}$ 。其它所有边的容量${\displaystyle M\geq 2}$ 。 使用福特-富尔克森算法可找到三条增广路径，分别为${\displaystyle p_{1}=\{s,v_{4},v_{3},v_{2},v_{1},t\}}$ 、${\displaystyle p_{2}=\{s,v_{2},v_{3},v_{4},t\}}$ 、${\displaystyle p_{3}=\{s,v_{1},v_{2},v_{3},t\}}$ .

步骤	增广路径	发送流	剩余容量
			${\displaystyle e_{1}}$	${\displaystyle e_{2}}$	${\displaystyle e_{3}}$
0			${\displaystyle r^{0}=1}$	${\displaystyle r}$	${\displaystyle 1}$
1	${\displaystyle \{s,v_{2},v_{3},t\}}$	${\displaystyle 1}$	${\displaystyle r^{0}}$	${\displaystyle r^{1}}$	${\displaystyle 0}$
2	${\displaystyle p_{1}}$	${\displaystyle r^{1}}$	${\displaystyle r^{2}}$	${\displaystyle 0}$	${\displaystyle r^{1}}$
3	${\displaystyle p_{2}}$	${\displaystyle r^{1}}$	${\displaystyle r^{2}}$	${\displaystyle r^{1}}$	${\displaystyle 0}$
4	${\displaystyle p_{1}}$	${\displaystyle r^{2}}$	${\displaystyle 0}$	${\displaystyle r^{3}}$	${\displaystyle r^{2}}$
5	${\displaystyle p_{3}}$	${\displaystyle r^{2}}$	${\displaystyle r^{2}}$	${\displaystyle r^{3}}$	${\displaystyle 0}$

注意在步骤1和步骤5之后,边${\displaystyle e_{1}}$ 、${\displaystyle e_{2}}$ 、${\displaystyle e_{3}}$ 的残留容量都可以表示为${\displaystyle r^{n}}$ 、${\displaystyle r^{n+1}}$ 或${\displaystyle 0}$ ，同时，对于一些特殊的${\displaystyle n\in \mathbb {N} }$ 这意味着算法可以通过${\displaystyle p_{1}}$ 、${\displaystyle p_{2}}$ 、${\displaystyle p_{1}}$ 与 ${\displaystyle p_{3}}$ 无限增广，并且残留容量总处于一个循环。在步骤5之后网络的流为${\displaystyle 1+2(r^{1}+r^{2})}$ ，如果继续用以上的算法增广，总的流将向${\displaystyle \textstyle 1+2\sum _{i=1}^{\infty }r^{i}=3+2r}$ 趋近，但最大流为${\displaystyle 2M+1}$ 。在这个样例中，算法将永远不会停止，且结果也不会向实际的最大流趋近。^[4]

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)) 

使用样例

>>> 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 

应用

二分图的最大匹配

最大不相交路径

参考文献

1. Laung-Terng Wang, Yao-Wen Chang, Kwang-Ting (Tim) Cheng. Electronic Design Automation: Synthesis, Verification, and Test. Morgan Kaufmann. 2009: 204. ISBN 0080922007. 
2. Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms. MIT Press. 2009: 714. ISBN 0262258102. 
3. Ford, L. R.; Fulkerson, D. R. Maximal flow through a network. Canadian Journal of Mathematics. 1956, 8: 399. doi:10.4153/CJM-1956-045-5. 
4. Zwick, Uri. The smallest networks on which the Ford–Fulkerson maximum flow procedure may fail to terminate. Theoretical Computer Science. 21 August 1995, 148 (1): 165–170. doi:10.1016/0304-3975(95)00022-O. 

• 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.