アルゴリズム
編集
グラフ
G
(
V
,
E
)
{\displaystyle G(V,E)}
u
{\displaystyle u}
v
{\displaystyle v}
c
(
u
,
v
)
{\displaystyle c(u,v)}
f
(
u
,
v
)
=
0
{\displaystyle f(u,v)=0}
s
{\displaystyle s}
t
{\displaystyle t}
f
(
u
,
v
)
≤
c
(
u
,
v
)
{\displaystyle \ f(u,v)\leq c(u,v)}
u
{\displaystyle u}
v
{\displaystyle v}
f
(
u
,
v
)
=
−
f
(
v
,
u
)
{\displaystyle \ f(u,v)=-f(v,u)}
u
{\displaystyle u}
v
{\displaystyle v}
u
{\displaystyle u}
v
{\displaystyle v}
a
{\displaystyle a}
v
{\displaystyle v}
u
{\displaystyle u}
b
{\displaystyle b}
f
(
u
,
v
)
=
a
−
b
{\displaystyle f(u,v)=a-b}
f
(
v
,
u
)
=
b
−
a
{\displaystyle f(v,u)=b-a}
∑
v
f
(
u
,
v
)
=
0
⟺
f
i
n
(
u
)
=
f
o
u
t
(
u
)
{\displaystyle \ \sum _{v}f(u,v)=0\Longleftrightarrow f_{in}(u)=f_{out}(u)}
s
{\displaystyle s}
t
{\displaystyle t}
u
{\displaystyle u}
すなわち、ネットワーク上のフローは、アルゴリズムの毎回の適用後に常に正当なものとなる。ここで、残余ネットワーク
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)}
u
,
v
{\displaystyle u,v}
u
,
v
{\displaystyle u,v}
v
,
u
{\displaystyle v,u}
E
=
E
f
{\displaystyle E=E_{f}}
アルゴリズム フォード・ファルカーソン
入力 フロー容量
c
{\displaystyle \,c}
s
{\displaystyle \,s}
t
{\displaystyle \,t}
G
{\displaystyle \,G}
出力
s
{\displaystyle \,s}
t
{\displaystyle \,t}
f
{\displaystyle \,f}
全ての枝
(
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}
c
f
(
p
)
=
min
{
c
f
(
u
,
v
)
|
(
u
,
v
)
∈
p
}
{\displaystyle \,c_{f}(p)=\min\{c_{f}(u,v)\;|\;(u,v)\in p\}}
(
u
,
v
)
∈
p
{\displaystyle (u,v)\in p}
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)}
経路は、
G
f
(
V
,
E
f
)
{\displaystyle G_{f}(V,E_{f})}
幅優先探索 や深さ優先探索 を行うことで得られる。前者の場合を特にエドモンズ-カープアルゴリズム と呼ぶ。
フロー増加道をグラフ上で既に確立されているフローに追加していくと、最終的にフロー増加道が見つからなくなり、最大フローが得られる。しかし、そのような状態に到達するかどうかは不確実であり、単にアルゴリズムが完了した場合は解が正しいということしか保証できない。アルゴリズムが無限に実行される場合、そのフローは最大フローに近づいているかどうかも不明である。ただし、そのような状態はフローの値が無理数の場合でしか発生しない。容量が整数の場合、フォード・ファルカーソンの実行時間の上限は O Ef ) であり、E はグラフ内の枝数、f はグラフの最大フローである。これは、増加道が O (E ) 回まで見つけることができ、毎回少なくともフローが 1 増加するためである。
フォード・ファルカーソンのアルゴリズムの派生として、エドモンズ-カープアルゴリズム がある。これは、終了することが保証されており、最大フローと実行時間が独立で、実行時間は O (VE 2 ) となる。
以下の例は、4ノードのフローネットワークでフォード・ファルカーソンのアルゴリズムを適用する様子を最初の数ステップだけ図示したものである。始点は A で終点は D 。増加道は深さ優先探索 で探し、隣接ノードは辞書順で調べる。この例では、アルゴリズムの最悪ケースを示している。各ステップではフローは1ずつしか増えない。この場合、幅優先探索 で経路を求めると、2ステップで完了する。
経路
容量
フローネットワーク
初期状態のフローネットワーク
A
,
B
,
C
,
D
{\displaystyle A,B,C,D}
min
(
c
f
(
A
,
B
)
,
c
f
(
B
,
C
)
,
c
f
(
C
,
D
)
)
{\displaystyle \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
)
)
{\displaystyle =\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
)
{\displaystyle =\min(1000-0,1-0,1000-0)}
=
1
{\displaystyle =1}
A
,
C
,
B
,
D
{\displaystyle A,C,B,D}
min
(
c
f
(
A
,
C
)
,
c
f
(
C
,
B
)
,
c
f
(
B
,
D
)
)
{\displaystyle \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
)
)
{\displaystyle =\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
)
{\displaystyle =\min(1000-0,0-(-1),1000-0)}
=
1
{\displaystyle =1}
1998ステップ後…
最終的なフローネットワーク
経路 A,C,B,D を見つけたとき、C から B へフローが押し戻される点に注意されたい。
参考文献
編集
^ T. コルメン、R. リベスト、C. シュタイン、C. ライザーソン『アルゴリズムイントロダクション』（第3版）近代科学社、2013年12月17日（原著2009-7-31）。ISBN 476490408X 。
外部リンク
編集
ウィキメディア・コモンズには、フォード・ファルカーソンのアルゴリズムに関するカテゴリがあります。