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

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

アルゴリズム

このアルゴリズムはフォード・ファルカーソンのアルゴリズムとほぼ同じだが、増加道を探索するときの順序が定義されている点だけが異なる。それは、各辺が単位長としたときの幅優先探索である。 の実行時間は、各増加道の探索に  の時間がかかり、 個の辺のうち毎回少なくとも1つが飽和し、飽和した辺と始点を結ぶ増加道が前回より短くなることはなく、増加道の長さの上限は  である。もう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

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