エドモンズ・カープのアルゴリズム

エドモンズ・カープのアルゴリズム

エドモンズ・カープのアルゴリズムは、フローネットワークにおける最大フロー問題を解くためのアルゴリズムの一つです。このアルゴリズムは、フォード・ファルカーソンのアルゴリズムを基にしており、増加道を探索する際に幅優先探索を用いる点が特徴です。

アルゴリズムの概要

エドモンズ・カープのアルゴリズムは、フォード・ファルカーソンのアルゴリズムと同様に、残余ネットワークにおいて増加道を繰り返し探索し、フローを増加させていくことで最大フローを求めます。ただし、増加道の選択方法が異なります。フォード・ファルカーソンのアルゴリズムでは任意の増加道を選択できますが、エドモンズ・カープのアルゴリズムでは、幅優先探索によって最短の増加道を選択します。

計算量

エドモンズ・カープのアルゴリズムの計算量は、最悪の場合でもO(VE^2)となります。ここで、Vはグラフの頂点数、Eは辺数を表します。これは、各増加道の探索にO(E)の時間がかかり、増加道の長さは最大でVであるため、増加道の探索を最大でVE回繰り返す必要があるためです。

他のアルゴリズムとの比較

エドモンズ・カープのアルゴリズムは、O(V^3)の計算量を持つrelabel-to-frontアルゴリズムと比較すると、漸近的には劣ります。しかし、辺が少ない疎なグラフにおいては、relabel-to-frontアルゴリズムよりも高速に動作することが知られています。また、DinicのアルゴリズムはO(V^2E)の計算量で動作しますが、追加の技法が含まれています。

アルゴリズムの詳細

1. 初期化: すべての辺のフローを0に設定します。
2. 増加道の探索: 幅優先探索を用いて、始点から終点への最短の増加道を見つけます。この際、各辺の残余容量（容量から現在のフローを引いた値）を考慮します。
3. フローの増加: 見つかった増加道に沿って、可能な限り最大のフローを流します。このフロー量は、増加道上の最小残余容量によって決まります。
4. 残余ネットワークの更新: フローを増加させた後、残余ネットワークを更新します。増加道に沿ってフローを増加させた辺の残余容量は減少し、逆向きの辺の残余容量は増加します。
5. 終了条件: 増加道が見つからなくなるまで、ステップ2から4を繰り返します。増加道が見つからなくなったら、現在のフローが最大フローとなります。

擬似コード

algorithm EdmondsKarp
input:
C[1..n, 1..n] (容量配列)
E[1..n, 1..?] (隣接リスト)
s (始点)
t (終点)
output:
f (最大フロー値)
F (最大値の正当なフローを与えるマトリクス)
f := 0 (初期フローはゼロ)
F := array(1..n, 1..n) (u から v への残余容量は C[u,v] - F[u,v])
forever
m, P := BreadthFirstSearch(C, E, s, t)
if m = 0
break
f := f + m
(バックトラックし、フローを書く)
v := t
while v ≠ s
u := P[v]
F[u,v] := F[u,v] + m
F[v,u] := F[v,u] - m
v := u
return (f, F)

algorithm BreadthFirstSearch
input:
C, E, s, t
output:
M[t] (見つかった道の容量)
P (親テーブル)
P := array(1..n)
for u in 1..n
P[u] := -1
P[s] := -2 (始点を再発見したのではないことを確認するため)
M := array(1..n) (見つけた道の容量)
M[s] := ∞
Q := queue()
Q.push(s)
while Q.size() > 0
u := Q.pop()
for v in E[u]
(まだ容量があり、v がまだ探索されていなかった場合)
if C[u,v] - F[u,v] > 0 and P[v] = -1
P[v] := u
M[v] := min(M[u], C[u,v] - F[u,v])
if v ≠ t
Q.push(v)
else
return M[t], P
return 0, P

例

7つのノードからなるネットワーク（Aが始点、Gが終点）を考えます。各辺の容量は以下のようになっています。

各辺にはf/cと表記されており、fは現在のフロー、cは容量を表します。残余容量は、c_f(u, v) = c(u, v) - f(u, v)で計算されます。例えば、辺(A, D)の容量が3で現在のフローが0の場合、残余容量は3です。また、フローが負の場合、残余容量は増加することに注意が必要です。

エドモンズ・カープのアルゴリズムで発見する増加道は、最短経路です。このアルゴリズムによって求められる最大フローは、最小カットの容量と等しくなります。この例では、最小カットは{A, B, C, E}と{D, F, G}に分割され、その容量はc(A, D) + c(C, D) + c(E, G) = 3 + 1 + 1 = 5となります。

実装例（Java）

（Javaでの具体的な実装例は、ここでは省略します。必要に応じて、具体的なコードを記述してください。）

まとめ

エドモンズ・カープのアルゴリズムは、フローネットワークにおける最大フロー問題を効率的に解くための重要なアルゴリズムです。幅優先探索を用いることで、フォード・ファルカーソンのアルゴリズムよりも計算量を改善し、疎なグラフにおいて特に有効です。

参考文献

* Herbert S. Wilf, Algorithms and Complexity (see pages 63 - 69)

もう一度検索