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

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

アルゴリズム

このアルゴリズムはフォード・ファルカーソンのアルゴリズムとほぼ同じだが、増加道を探索するときの順序が定義されている点だけが異なる。それは、各辺が単位長としたときの幅優先探索である。$O(|V| \cdot |E|^2)$ の実行時間は、各増加道の探索に $O(|E|)$ の時間がかかり、$E$ 個の辺のうち毎回少なくとも1つが飽和し、飽和した辺と始点を結ぶ増加道が前回より短くなることはなく、増加道の長さの上限は $V$ である。もう1つのこのアルゴリズムの特性として、最短増加道の長さは単調に増大する。アルゴリズムの妥当性の証明は Introduction to Algorithms にある。

擬似コード

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$ は容量を表す。$u$ から $v$ の残余容量は $c_f(u,v)=c(u,v)-f(u,v)$ で表される（容量から既に使われている分のフローを差し引いた値）。$u$ から $v$ へのフローが負の場合、残余容量は却って増える。

容量	経路（道）
	ネットワーク
$\min(c_f(A,D),c_f(D,E),c_f(E,G)) =$ $\min(3-0,2-0,1-0) =$ $\min(3,2,1) = 1$	$A,D,E,G$
$\min(c_f(A,D),c_f(D,F),c_f(F,G)) =$ $\min(3-1,6-0,9-0) =$ $\min(2,6,9) = 2$	$A,D,F,G$
$\min(c_f(A,B),c_f(B,C),c_f(C,D),c_f(D,F),c_f(F,G)) =$ $\min(3-0,4-0,1-0,6-2,9-2) =$ $\min(3,4,1,4,7) = 1$	$A,B,C,D,F,G$
$\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)) =$ $\min(3-1,4-1,2-0,0--1,6-3,9-3) =$ $\min(2,3,2,1,3,6) = 1$	$A,B,C,E,D,F,G$

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

Javaでの実装

import java.io.*;
 
class FlowGraph
{
        public static final int WHITE = 0, GRAY = 1, BLACK = 2;
        private double[][] flow, capacity, res_capacity;
        private int[] parent, color, queue;
        private double[] min_capacity;
        private int size, source, sink, first, last;
        private double max_flow;
 
        public FlowGraph(String fileName)
        {
                .. // 入力テキストファイルから、"size" 値、"capacity[size][size]" 配列、
                   // "source" および "sink" ノードのインデックス値（0始点）
                   // を読み込む。
                maxFlow();
        }
 
        private void maxFlow()  // 計算量 O(V³E) のエドモンズ・カープのアルゴリズム
        {
                flow = new double[size][size];
                res_capacity = new double[size][size];
                parent = new int[size];
                min_capacity = 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++)
                                res_capacity[i][j] = capacity[i][j];
 
                while (BFS(source))
                {
                        max_flow += min_capacity[sink];
                        int v = sink, u;
                        while (v != source)
                        {
                                u = parent[v];
                                flow[u][v] += min_capacity[sink];
                                flow[v][u] -= min_capacity[sink];
                                res_capacity[u][v] -= min_capacity[sink];
                                res_capacity[v][u] += min_capacity[sink];
                                v = u;
                        }
                }
        }
 
        private boolean BFS(int source)  // O(V²) の幅優先探索
        {
                for (int i = 0; i < size; i++)
                {
                        color[i] = WHITE;
                        min_capacity[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 && res_capacity[v][u] > 0)
                                {
                                        min_capacity[u] = Math.min(min_capacity[v], res_capacity[v][u]);
                                        parent[u] = v;
                                        color[u] = GRAY;
                                        if (u == sink) return true;
                                        queue[last++] = u;
                                }
                }
                return false;
        }
 
        public void toFile(String fileName)
        {
                .. // 出力ファイルに結果を書く（"flow" 配列と "max_flow" 値）
                   // "main()" メソッドから呼び出す。
        }
}

参考文献

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