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

エドモンズ・カープのアルゴリズム（英: Edmonds-Karp algorithm）は、フローネットワークの最大フロー問題を解くフォード・ファルカーソンのアルゴリズムの実装の一種であり、${\displaystyle O(VE^{2})}$ の計算量である。${\displaystyle O(V^{3})}$ のrelabel-to-front アルゴリズムに比べると漸近的に遅いが、（辺の少ない）疎なグラフでは速い。このアルゴリズムは1970年にロシア人科学者 Dinic が発表し^[1]、それとは独立に1972年にジャック・エドモンズとリチャード・カープが発表した^[2]（発見はこちらの方が早かった）。Dinic のアルゴリズムには追加の技法が含まれており、計算量は ${\displaystyle O(V^{2}E)}$ となっている。

アルゴリズム

このアルゴリズムはフォード・ファルカーソンのアルゴリズムとほぼ同じだが、増加道を探索するときの順序が定義されている点だけが異なる。それは、各辺が単位長としたときの幅優先探索である。${\displaystyle O(VE^{2})}$ の実行時間は、各増加道の探索に ${\displaystyle O(E)}$ の時間がかかり、${\displaystyle E}$ 個の辺のうち毎回少なくとも1つが飽和し、飽和した辺と始点を結ぶ増加道が前回より短くなることはなく、増加道の長さの上限は ${\displaystyle V}$ である。もう1つのこのアルゴリズムの特性として、最短増加道の長さは単調に増大する。アルゴリズムの妥当性の証明は書籍『アルゴリズムイントロダクション』（ISBN 476490408X） にある^[3]。

擬似コード

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 が終点）について、以下のように容量が定義されている。

各辺にある ${\displaystyle f/c}$ で、${\displaystyle f}$ は現在のフロー、${\displaystyle c}$ は容量を表す。${\displaystyle u}$ から ${\displaystyle v}$ の残余容量は ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$ で表される（容量から既に使われている分のフローを差し引いた値）。${\displaystyle u}$ から ${\displaystyle v}$ へのフローが負の場合、残余容量は却って増える。

容量	経路（道）
	ネットワーク
${\displaystyle \min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))=}$ ${\displaystyle \min(3-0,2-0,1-0)=}$ ${\displaystyle \min(3,2,1)=1}$	${\displaystyle A,D,E,G}$
${\displaystyle \min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))=}$ ${\displaystyle \min(3-1,6-0,9-0)=}$ ${\displaystyle \min(2,6,9)=2}$	${\displaystyle A,D,F,G}$
${\displaystyle \min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))=}$ ${\displaystyle \min(3-0,4-0,1-0,6-2,9-2)=}$ ${\displaystyle \min(3,4,1,4,7)=1}$	${\displaystyle A,B,C,D,F,G}$
${\displaystyle \min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f}(D,F),c_{f}(F,G))=}$ ${\displaystyle \min(3-1,4-1,2-0,0--1,6-3,9-3)=}$ ${\displaystyle \min(2,3,2,1,3,6)=1}$	${\displaystyle A,B,C,E,D,F,G}$

このアルゴリズムで発見する増加道（赤で示されている）の長さが決して減少しない点に注意されたい。発見した道は、その時点の最短である。見つかったフローは、グラフの始点と終点を分離するように横切る最小カットをまたぐ容量と等価である。このグラフには最小カットは1つしかなく、${\displaystyle \{A,B,C,E\}}$ と ${\displaystyle \{D,F,G\}}$ に分割する分け方であり、その容量は ${\displaystyle c(A,D)+c(C,D)+c(E,G)=3+1+1=5}$ である。

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;
    }
}

脚注

参考文献

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

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）