福特-富爾克森方法 (英語:Ford–Fulkerson method ),又稱福特-富爾克森算法 (Ford–Fulkerson algorithm ),是一類計算網絡流 的最大流 的貪心算法 。之所以稱之為「方法」而不是「算法」,是因為它尋找增廣路徑的方式並不是完全確定的,而是有幾種不同時間複雜度 的實現方式[ 1] [ 2] 。它在1956年由小萊斯特·倫道夫·福特 及德爾伯特·雷·富爾克森 [ 3] 發表。「福特-富爾克森」這個名詞通常也指代埃德蒙茲-卡普算法 ,這是一個特殊的福特-富爾克森算法實現。
算法的思想如下:只要有一條從源點(開始節點)到匯點(結束節點)的路徑,在路徑的所有邊上都有可用容量,就沿着這條路徑發送一個流,流量由路徑上的最小容量限制。 然後再找到另一條路徑,一直到網絡中不存在這種路徑為止。 一條有可用容量的路徑被稱為一條增廣路徑。
設
G
(
V
,
E
)
{\displaystyle G(V,E)}
為一個圖,並且為每條從
u
{\displaystyle u}
到
v
{\displaystyle v}
的邊
(
u
,
v
)
{\displaystyle (u,v)}
設置一個最大流量
c
(
u
,
v
)
{\displaystyle c(u,v)}
,並且初始化當前流量
f
(
u
,
v
)
=
0
{\displaystyle f(u,v)=0}
。下面是該算法每一步的實現:
容量限制 :
∀
(
u
,
v
)
∈
E
,
f
(
u
,
v
)
≤
c
(
u
,
v
)
{\displaystyle \forall (u,v)\in E,f(u,v)\leq c(u,v)}
每條邊上的流都不能超出邊的最大流量。
反向對稱 :
∀
(
u
,
v
)
∈
E
,
f
(
u
,
v
)
=
−
f
(
v
,
u
)
{\displaystyle \forall (u,v)\in E,f(u,v)=-f(v,u)}
從
u
{\displaystyle u}
到
v
{\displaystyle v}
的流量一定是從
v
{\displaystyle v}
到
u
{\displaystyle u}
的流量的相反數(見樣例)。
流量守恆 :
∀
u
∈
V
:
u
≠
s
,
u
≠
t
⇒
∑
w
∈
V
f
(
u
,
w
)
=
0
{\displaystyle \forall u\in V:u\neq s,u\neq t\Rightarrow \sum _{w\in V}f(u,w)=0}
除非
u
{\displaystyle u}
是源點
s
{\displaystyle s}
或匯點
t
{\displaystyle t}
,一個節點的淨流量為零。
f的值 :
∑
(
s
,
u
)
∈
E
f
(
s
,
u
)
=
∑
(
v
,
t
)
∈
E
f
(
v
,
t
)
{\displaystyle \sum _{(s,u)\in E}f(s,u)=\sum _{(v,t)\in E}f(v,t)}
從源點
s
{\displaystyle s}
流出的流量一定等於匯點
t
{\displaystyle t}
接收的流量。
這意味着每輪計算之後通過網絡的都是一個流。我們定義殘留網絡
G
f
(
V
,
E
f
)
{\displaystyle G_{f}(V,E_{f})}
是一個網絡的剩餘流量
c
f
(
u
,
v
)
=
c
(
u
,
v
)
−
f
(
u
,
v
)
{\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}
。注意殘留網絡可以設置從
v
{\displaystyle v}
到
u
{\displaystyle u}
的流量,即使在原先的網絡中不允許這種情況產生:如果
c
(
v
,
u
)
=
0
{\displaystyle c(v,u)=0}
但
f
(
u
,
v
)
>
0
{\displaystyle f(u,v)>0}
,那麼
c
f
(
v
,
u
)
=
c
(
v
,
u
)
−
f
(
v
,
u
)
=
f
(
u
,
v
)
>
0
{\displaystyle c_{f}(v,u)=c(v,u)-f(v,u)=f(u,v)>0}
:也即,從
u
{\displaystyle u}
到
v
{\displaystyle v}
的流量給從
v
{\displaystyle v}
到
u
{\displaystyle u}
的流量提供了額外的剩餘量。
算法 福特-富爾克森
輸入 給定一張邊的容量為
c
{\displaystyle c}
的圖
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
,源點
s
{\displaystyle s}
以及匯點
t
{\displaystyle t}
。
輸出 在網絡
G
{\displaystyle G}
中,從
s
{\displaystyle s}
到
t
{\displaystyle t}
的最大流
f
{\displaystyle f}
。
初始化網絡流量
f
←
0
{\displaystyle f\leftarrow 0}
、殘留網絡
G
f
←
G
{\displaystyle G_{f}\leftarrow G}
。對於圖的每一條邊
(
u
,
v
)
{\displaystyle (u,v)}
,初始化流量
f
(
u
,
v
)
←
0
{\displaystyle f(u,v)\leftarrow 0}
。
只要
G
f
{\displaystyle G_{f}}
中還存在一條從
s
{\displaystyle s}
到
t
{\displaystyle t}
的路徑
p
{\displaystyle p}
,使對於每一條邊
(
u
,
v
)
∈
p
{\displaystyle (u,v)\in p}
,都有
c
f
(
u
,
v
)
>
0
{\displaystyle c_{f}(u,v)>0}
:
設置路徑
p
{\displaystyle p}
本次應發送的流量為路徑最小剩餘流量:
c
f
(
p
)
←
min
(
u
,
v
)
∈
p
c
f
(
u
,
v
)
{\displaystyle c_{f}(p)\leftarrow \min _{(u,v)\in p}c_{f}(u,v)}
。
更新網絡流量
f
←
f
+
c
f
(
p
)
{\displaystyle f\leftarrow f+c_{f}(p)}
。
對於每一條邊
(
u
,
v
)
∈
p
{\displaystyle (u,v)\in p}
,更新
G
f
{\displaystyle G_{f}}
的剩餘流量:
f
(
u
,
v
)
←
f
(
u
,
v
)
+
c
f
(
p
)
{\displaystyle f(u,v)\leftarrow f(u,v)+c_{f}(p)}
(在路徑中「發送」流)
f
(
v
,
u
)
←
f
(
v
,
u
)
−
c
f
(
p
)
{\displaystyle f(v,u)\leftarrow f(v,u)-c_{f}(p)}
(這個流在之後可以被「發送」回來)
步驟2中的路徑
p
{\displaystyle p}
可以用廣度優先搜索 或深度優先搜索 在
G
f
(
V
,
E
f
)
{\displaystyle G_{f}(V,E_{f})}
中找到。如果使用了廣度優先搜索 ,這個算法就是Edmonds–Karp算法 。
當步驟2中找不到可行路徑時,
s
{\displaystyle s}
就無法在殘留網絡中到達
t
{\displaystyle t}
。設
S
{\displaystyle S}
是在殘留網絡中
s
{\displaystyle s}
可以到達的節點的集合,然後從
S
{\displaystyle S}
到
V
{\displaystyle V}
的其餘部分的網絡一方面等於我們找到的從
s
{\displaystyle s}
到
t
{\displaystyle t}
的所有流的總流量,另一方面所有這樣的流量組成了一個上限。這說明我們找到的流是最大的。參見最大流最小割定理 。
如果圖
G
(
V
,
E
)
{\displaystyle G(V,E)}
有多個源點和匯點,可以按如下方法處理:設
T
=
{
t
|
t
为 目 标 点
}
{\displaystyle T=\{t|t{\text{为 目 标 点 }}\}}
,
S
=
{
s
|
s
为 源 点
}
{\displaystyle S=\{s|s{\text{为 源 点 }}\}}
。 添加一個新源點
s
∗
{\displaystyle s^{*}}
與所有源點有一條邊
(
s
∗
,
s
)
{\displaystyle (s^{*},s)}
相連,容量
c
(
s
∗
,
s
)
=
d
s
(
d
s
=
∑
(
s
,
u
)
∈
E
c
(
s
,
u
)
)
{\displaystyle c(s^{*},s)=d_{s}\;(d_{s}=\sum _{(s,u)\in E}c(s,u))}
。添加一個新匯點
t
∗
{\displaystyle t^{*}}
與所有匯點
(
t
,
t
∗
)
{\displaystyle (t,t^{*})}
有一條邊相連,容量
c
(
t
,
t
∗
)
=
d
t
(
d
t
=
∑
(
v
,
t
)
∈
E
c
(
v
,
t
)
)
{\displaystyle c(t,t^{*})=d_{t}\;(d_{t}=\sum _{(v,t)\in E}c(v,t))}
。然後執行福特-富爾克森算法。
同樣的,如果節點
u
{\displaystyle u}
有通過限制
d
u
{\displaystyle d_{u}}
,可將這個節點用兩個節點
u
i
n
,
u
o
u
t
{\displaystyle u_{in},u_{out}}
替換,用一條邊
(
u
i
n
,
u
o
u
t
)
{\displaystyle (u_{in},u_{out})}
相連,容量為
c
(
u
i
n
,
u
o
u
t
)
=
d
u
{\displaystyle c(u_{in},u_{out})=d_{u}}
。然後執行福特-富爾克森算法。
下面的樣例演示了福特-富爾克森在一張有4個節點,源點為
A
{\displaystyle A}
,匯點為
D
{\displaystyle D}
的圖中的第一輪計算。 這個例子顯示了算法在最壞情況下的行為。在每一輪算法中,只有
1
{\displaystyle 1}
的流量被發送至網絡中。如果算法改用寬度優先搜索,那麼只需要兩輪計算。
More information , ...
路徑
容量
網絡
原流
A
,
B
,
C
,
D
{\displaystyle A,B,C,D}
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
{\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}}}
A
,
C
,
B
,
D
{\displaystyle A,C,B,D}
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
{\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輪之後…
最終流
Close
注意當找到路徑
A
,
C
,
B
,
D
{\displaystyle A,C,B,D}
時,流是如何從
C
{\displaystyle C}
發送至
B
{\displaystyle B}
的。
右圖所示的網絡中源點為
s
{\displaystyle s}
,匯點為
t
{\displaystyle t}
邊
e
1
{\displaystyle e_{1}}
、
e
2
{\displaystyle e_{2}}
、
e
3
{\displaystyle e_{3}}
的容量為
1
{\displaystyle 1}
,
r
=
(
5
−
1
)
/
2
{\displaystyle r=({\sqrt {5}}-1)/2}
和
1
{\displaystyle 1}
,使
r
2
=
1
−
r
{\displaystyle r^{2}=1-r}
。其它所有邊的容量
M
≥
2
{\displaystyle M\geq 2}
。 使用福特-富爾克森算法可找到三條增廣路徑,分別為
p
1
=
{
s
,
v
4
,
v
3
,
v
2
,
v
1
,
t
}
{\displaystyle p_{1}=\{s,v_{4},v_{3},v_{2},v_{1},t\}}
、
p
2
=
{
s
,
v
2
,
v
3
,
v
4
,
t
}
{\displaystyle p_{2}=\{s,v_{2},v_{3},v_{4},t\}}
、
p
3
=
{
s
,
v
1
,
v
2
,
v
3
,
t
}
{\displaystyle p_{3}=\{s,v_{1},v_{2},v_{3},t\}}
.
注意在步驟1和步驟5之後,邊
e
1
{\displaystyle e_{1}}
、
e
2
{\displaystyle e_{2}}
、
e
3
{\displaystyle e_{3}}
的殘留容量都可以表示為
r
n
{\displaystyle r^{n}}
、
r
n
+
1
{\displaystyle r^{n+1}}
或
0
{\displaystyle 0}
,同時,對於一些特殊的
n
∈
N
{\displaystyle n\in \mathbb {N} }
這意味着算法可以通過
p
1
{\displaystyle p_{1}}
、
p
2
{\displaystyle p_{2}}
、
p
1
{\displaystyle p_{1}}
與
p
3
{\displaystyle p_{3}}
無限增廣,並且殘留容量總處於一個循環。在步驟5之後網絡的流為
1
+
2
(
r
1
+
r
2
)
{\displaystyle 1+2(r^{1}+r^{2})}
,如果繼續用以上的算法增廣,總的流將向
1
+
2
∑
i
=
1
∞
r
i
=
3
+
2
r
{\displaystyle \textstyle 1+2\sum _{i=1}^{\infty }r^{i}=3+2r}
趨近,但最大流為
2
M
+
1
{\displaystyle 2M+1}
。在這個樣例中,算法將永遠不會停止,且結果也不會向實際的最大流趨近。[ 4]
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
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 .