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

エドモンズ・カープのアルゴリズム（英: Edmonds-Karp algorithm）は、フローネットワークの最大フロー問題を解くフォード・ファルカーソンのアルゴリズムの実装の一種であり、formula_1 の計算量である。formula_2 のrelabel-to-front アルゴリズムに比べると漸近的に遅いが、（辺の少ない）疎なグラフでは速い。このアルゴリズムは1970年にロシア人科学者 Dinic が発表し、それとは独立に1972年にジャック・エドモンズとリチャード・カープが発表した（発見はこちらの方が早かった）。Dinic のアルゴリズムには追加の技法が含まれており、計算量は formula_3 となっている。
アルゴリズム.
このアルゴリズムはフォード・ファルカーソンのアルゴリズムとほぼ同じだが、増加道を探索するときの順序が定義されている点だけが異なる。それは、各辺が単位長としたときの幅優先探索である。formula_1 の実行時間は、各増加道の探索に formula_5 の時間がかかり、formula_6 個の辺のうち毎回少なくとも1つが飽和し、飽和した辺と始点を結ぶ増加道が前回より短くなることはなく、増加道の長さの上限は formula_7 である。もう1つのこのアルゴリズムの特性として、最短増加道の長さは単調に増大する。アルゴリズムの妥当性の証明は書籍『アルゴリズムイントロダクション』（ISBN 476490408X） にある。
擬似コード.
 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 が終点）について、以下のように容量が定義されている。
各辺にある formula_8 で、formula_9 は現在のフロー、formula_10 は容量を表す。formula_11 から formula_12 の残余容量は formula_13 で表される（容量から既に使われている分のフローを差し引いた値）。formula_11 から formula_12 へのフローが負の場合、残余容量は却って増える。
このアルゴリズムで発見する増加道（赤で示されている）の長さが決して減少しない点に注意されたい。発見した道は、その時点の最短である。見つかったフローは、グラフの始点と終点を分離するように横切る最小カットをまたぐ容量と等価である。このグラフには最小カットは1つしかなく、formula_16 と formula_17 に分割する分け方であり、その容量は formula_18 である。
Javaでの実装.
public class FlowGraph {
 public static final int WHITE = 0, GRAY = 1, BLACK = 2;
 private double[][] flow, capacity, resCapacity;
 private int[] parent, color, queue;
 private double[] minCapacity;
 private int size, source, sink, first, last;
 private double maxFlow;
 public FlowGraph(String fileName) {
 // 入力テキストファイルから
 // "size" 値
 // "capacity[size][size]" 配列
 // "source" および "sink" ノードのインデックス値（0始点）
 // を読み込む。
 edmondsKarp();
 // 出力ファイルに結果を書く（"flow" 配列と "maxFlow" 値）
 private void edmondsKarp() { // 計算量 O(V³E) のエドモンズ・カープのアルゴリズム
 flow = new double[size][size];
 resCapacity = new double[size][size];
 parent = new int[size];
 minCapacity = new double[size];
 color = new int[size];
 queue = new int[size];
 for (int i = 0; i < size; i++)
 for (int j = 0; j < size; j++)
 resCapacity[i][j] = capacity[i][j];
 while (BFS(source)) {
 maxFlow += minCapacity[sink];
 int v = sink, u;
 while (v != source) {
 u = parent[v];
 flow[u][v] += minCapacity[sink];
 flow[v][u] -= minCapacity[sink];
 resCapacity[u][v] -= minCapacity[sink];
 resCapacity[v][u] += minCapacity[sink];
 v = u;
 private boolean BFS(int source) { // O(V²) の幅優先探索
 for (int i = 0; i < size; i++) {
 color[i] = WHITE;
 minCapacity[i] = Double.MAX_VALUE;
 first = last = 0;
 queue[last++] = source;
 color[source] = GRAY;
 while (first != last) { // "queue" が空でないうちはループする
 int v = queue[first++];
 for (int u = 0; u < size; u++)
 if (color[u] == WHITE && resCapacity[v][u] > 0) {
 minCapacity[u] = Math.min(minCapacity[v], resCapacity[v][u]);
 parent[u] = v;
 color[u] = GRAY;
 if (u == sink) return true;
 queue[last++] = u;
 return false;