福特-富尔克森算法

/ 最大流 最小割 / 0 条评论 / 70浏览

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

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

目录 1 算法 1.1 伪代码 2 复杂度 3 样例 4 无法终止算法的样例 5 Python源码 5.1 使用样例 6 应用 7 参考文献 算法 设 � ( � , � ) {\displaystyle G(V,E)}为一个图，并且为每条从 � u到 � v的边 ( � , � ) (u,v)设置一个最大流量 � ( � , � ) c(u,v)，并且初始化当前流量 � ( � , � )

0 {\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)} 从 � u到 � v的流量一定是从 � v到 � u的流量的相反数（见样例）。 流量守恒: ∀ � ∈ � : � ≠ � , � ≠ � ⇒ ∑ � ∈ � � ( � , � )

0 {\displaystyle \forall u\in V:u\neq s,u\neq t\Rightarrow \sum _{w\in V}f(u,w)=0} 除非 � u是源点 � s或汇点 � t，一个节点的净流量为零。 f的值: ∑ ( � , � ) ∈ � � ( � , � )

∑ ( � , � ) ∈ � � ( � , � ) {\displaystyle \sum {(s,u)\in E}f(s,u)=\sum {(v,t)\in E}f(v,t)} 从源点 � s流出的流量一定等于汇点 � t接收的流量。 这意味着每轮计算之后通过网络的都是一个流。我们定义残留网络 � � ( � , � � ) {\displaystyle G{f}(V,E{f})}是一个网络的剩余流量 � � ( � , � )

� ( � , � ) − � ( � , � ) {\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}。注意残留网络可以设置从 � v到 � u的流量，即使在原先的网络中不允许这种情况产生：如果 � ( � , � )

0 {\displaystyle c(v,u)=0} 但 � ( � , � )

0 {\displaystyle f(u,v)>0}，那么 � � ( � , � )

� ( � , � ) − � ( � , � )

� ( � , � )

0 {\displaystyle 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。 初始化网络流量 � ← 0 {\displaystyle f\leftarrow 0}、残留网络 � � ← � {\displaystyle G_{f}\leftarrow G}。对于图的每一条边 ( � , � ) (u,v)，初始化流量 � ( � , � ) ← 0 {\displaystyle f(u,v)\leftarrow 0}。 只要 � � {\displaystyle G_{f}}中还存在一条从 � s到 � t的路径 � p，使对于每一条边 ( � , � ) ∈ � {\displaystyle (u,v)\in p}，都有 � � ( � , � )

0 {\displaystyle c_{f}(u,v)>0}： 设置路径 � p本次应发送的流量为路径最小剩余流量： � � ( � ) ← min ( � , � ) ∈ � � � ( � , � ) {\displaystyle c_{f}(p)\leftarrow \min {(u,v)\in p}c{f}(u,v)}。 更新网络流量 � ← � + � � ( � ) {\displaystyle f\leftarrow f+c_{f}(p)}。 对于每一条边 ( � , � ) ∈ � {\displaystyle (u,v)\in p}，更新 � � {\displaystyle G_{f}}的剩余流量： � ( � , � ) ← � ( � , � ) + � � ( � ) {\displaystyle f(u,v)\leftarrow f(u,v)+c_{f}(p)} （在路径中“发送”流） � ( � , � ) ← � ( � , � ) − � � ( � ) {\displaystyle f(v,u)\leftarrow f(v,u)-c_{f}(p)} （这个流在之后可以被“发送”回来） 步骤2中的路径 � p可以用广度优先搜索或深度优先搜索在 � � ( � , � � ) {\displaystyle G_{f}(V,E_{f})}中找到。如果使用了广度优先搜索，这个算法就是Edmonds–Karp算法。

当步骤2中找不到可行路径时， � s就无法在残留网络中到达 � t。设 � S是在残留网络中 � s可以到达的节点的集合，然后从 � S到 � V的其余部分的网络一方面等于我们找到的从 � s到 � 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))}。然后执行福特-富尔克森算法。

同样的，如果节点 � 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符号）, � E图中的边数， � f为最大流。 这是因为一条增广路径可以在 � ( � ) {\displaystyle O(E)}的时间复杂度内找到，每轮算法执行后流量的增长至少为 1 1。但是在极端情况下，算法有可能永远不会停止。

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

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

路径 容量 网络 原流 Ford-Fulkerson example 0.svg � , � , � , � {\displaystyle A,B,C,D} min ( � � ( � , � ) , � � ( � , � ) , � � ( � , � ) )

min ( � ( � , � ) − � ( � , � ) , � ( � , � ) − � ( � , � ) , � ( � , � ) − � ( � , � ) )

min ( 1000 − 0 , 1 − 0 , 1000 − 0 )

1 {\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}}} Ford-Fulkerson example 1.svg � , � , � , � {\displaystyle A,C,B,D} min ( � � ( � , � ) , � � ( � , � ) , � � ( � , � ) )

min ( � ( � , � ) − � ( � , � ) , � ( � , � ) − � ( � , � ) , � ( � , � ) − � ( � , � ) )

min ( 1000 − 0 , 0 − ( − 1 ) , 1000 − 0 )

1 {\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}}} Ford-Fulkerson example 2.svg 1998轮之后… 最终流 Ford-Fulkerson example final.svg 注意当找到路径 � , � , � , � {\displaystyle A,C,B,D}时，流是如何从 � C发送至 � B的。

无法终止算法的样例 Ford-Fulkerson forever.svg 右图所示的网络中源点为 � s，汇点为 � t边 � 1 e_{1}、 � 2 e_{2}、 � 3 e_{3}的容量为 1 1, �

( 5 − 1 ) / 2 {\displaystyle r=({\sqrt {5}}-1)/2}和 1 1，使 � 2

1 − � {\displaystyle r^{2}=1-r}。其它所有边的容量 � ≥ 2 {\displaystyle M\geq 2}。 使用福特-富尔克森算法可找到三条增广路径，分别为 � 1

{ � , � 4 , � 3 , � 2 , � 1 , � } {\displaystyle p_{1}={s,v_{4},v_{3},v_{2},v_{1},t}}、 � 2

{ � , � 2 , � 3 , � 4 , � } {\displaystyle p_{2}={s,v_{2},v_{3},v_{4},t}}、 � 3

{ � , � 1 , � 2 , � 3 , � } {\displaystyle p_{3}={s,v_{1},v_{2},v_{3},t}}.

步骤 增广路径 发送流 剩余容量 � 1 e_{1} � 2 e_{2} � 3 e_{3} 0 � 0

1 {\displaystyle r^{0}=1} � r 1 1 1 { � , � 2 , � 3 , � } {\displaystyle {s,v_{2},v_{3},t}} 1 1 � 0 {\displaystyle r^{0}} � 1 {\displaystyle r^{1}} 0 {\displaystyle 0} 2 � 1 p_{1} � 1 {\displaystyle r^{1}} � 2 r^{2} 0 {\displaystyle 0} � 1 {\displaystyle r^{1}} 3 � 2 p_{2} � 1 {\displaystyle r^{1}} � 2 r^{2} � 1 {\displaystyle r^{1}} 0 {\displaystyle 0} 4 � 1 p_{1} � 2 r^{2} 0 {\displaystyle 0} � 3 {\displaystyle r^{3}} � 2 r^{2} 5 � 3 p_3 � 2 r^{2} � 2 r^{2} � 3 {\displaystyle r^{3}} 0 {\displaystyle 0} 注意在步骤1和步骤5之后,边 � 1 e_{1}、 � 2 e_{2}、 � 3 e_{3}的残留容量都可以表示为 � � {\displaystyle r^{n}}、 � � + 1 {\displaystyle r^{n+1}}或 0 {\displaystyle 0}，同时，对于一些特殊的 � ∈ � {\displaystyle n\in \mathbb {N} }这意味着算法可以通过 � 1 p_{1}、 � 2 p_{2}、 � 1 p_{1}与 � 3 p_3无限增广，并且残留容量总处于一个循环。在步骤5之后网络的流为 1 + 2 ( � 1 + � 2 ) {\displaystyle 1+2(r^{1}+r^{2})}，如果继续用以上的算法增广，总的流将向 1 + 2 ∑ �

1 ∞ � �

3 + 2 � {\displaystyle \textstyle 1+2\sum _{i=1}^{\infty }r^{i}=3+2r}趋近，但最大流为 2 � + 1 {\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 应用 二分图的最大匹配

最大不相交路径

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为:

↓ ← → ↑