福特-富尔克森方法（），又稱福特-富尔克森算法（），是一类计算网络流的最大流的贪心算法。之所以称之为“方法”而不是“算法”，是因为它寻找增广路径的方式并不是完全确定的，而是有几种不同时间复杂度的实现方式。它在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。
:# 初始化网络流量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的流量被发送至网络中。如果算法改用宽度优先搜索，那么只需要两轮计算。
注意当找到路径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 \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 \}.
注意在步骤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源码
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
应用
二分图的最大匹配
最大不相交路径
参考文献
*
*
*
评论 (0)