フォード・ファルカーソン法とは？グラフの最大流を求めるアルゴリズムを解説

フォード・ファルカーソン（Ford-Fulkerson）アルゴリズムは、与えられたグラフにおいて、始点（ソース）から終点（シンク）までの最大フロー（最大流）を求めるために用いられる古典的なアルゴリズムです。このグラフでは、すべての辺に「容量」が設定されており、ソースとシンクという2つの頂点が指定されます。ソース頂点は外向きの辺のみを持ち、シンク頂点は内向きの辺のみを持つという特徴があります。

アルゴリズムが満たすべき制約条件

• 各辺に流れるフローは、その辺に設定された容量を超えてはならない。
• ソースとシンクを除くすべての頂点において、流入するフローの合計と流出するフローの合計は等しくなければならない。

入力と出力

入力：隣接行列
0 10 0 10 0  0
0  0 4  2 8  0
0  0 0  0 0 10
0  0 0  0 9  0
0  0 6  0 0 10
0  0 0  0 0  0

出力：
Maximum flow is: 19

アルゴリズムの流れ

このアルゴリズムは、BFS（幅優先探索）を使って増加パス（増加路）を見つけながら、残余グラフを更新していく仕組みです。

bfs(vert, start, sink)

入力： 頂点リスト、開始ノード、シンクノード

出力： シンクに到達できた場合は true を返す。

Begin
    最初にすべてのノードを未訪問としてマークする
    開始ノードを訪問済みとする
    開始ノードの先行ノードは φ とする
    開始ノードをキュー qu に挿入する
    qu が空でない間、以下を繰り返す
        キューから要素を取り出し、頂点 u とする
        残余グラフ内のすべての頂点 i について、
            u と i が接続しており、i が未訪問であれば、
                頂点 i をキューに追加する
                i の先行ノードを u とする
                i を訪問済みとしてマークする
        繰り返し終了
    繰り返し終了
    シンク頂点が訪問済みであれば true を返す
End

fordFulkerson(vert, source, sink)

入力： 頂点リスト、ソース頂点、シンク頂点

出力： ソースからシンクまでの最大フロー

Begin
    残余グラフを作成し、元のグラフをコピーする
    bfs(vert, source, sink) が true を返す間、以下を繰り返す
        pathFlow := ∞
        v := シンク頂点
        v ≠ 開始頂点である間、以下を繰り返す
            u := v の先行ノード
            pathFlow := pathFlow と residualGraph[u, v] の最小値
            v := v の先行ノード
        繰り返し終了

        v := シンク頂点
        v ≠ 開始頂点である間、以下を繰り返す
            u := v の先行ノード
            residualGraph[u,v] := residualGraph[u,v] − pathFlow
            residualGraph[v,u] := residualGraph[v,u] + pathFlow
            v := v の先行ノード
        繰り返し終了

        maxFlow := maxFlow + pathFlow
    繰り返し終了
    maxFlow を返す
End

C++による実装例

#include<iostream>
#include<queue>
#define NODE 6
using namespace std;

typedef struct node {
    int val;
    int state; //状態（訪問済みかどうか）
    int pred;  //先行ノード
}node;

int minimum(int a, int b) {
    return (a<b)?a:b;
}

int resGraph[NODE][NODE];

int graph[NODE][NODE] = {
    {0, 10, 0, 10, 0, 0},
    {0, 0, 4, 2, 8, 0},
    {0, 0, 0, 0, 0, 10},
    {0, 0, 0, 0, 9, 0},
    {0, 0, 6, 0, 0, 10},
    {0, 0, 0, 0, 0, 0}
};

// BFSで増加パスを探索する関数
int bfs(node *vert, node start, node sink) {
    node u;
    int i, j;
    queue<node> que;

    for(i = 0; i<NODE; i++) {
        vert[i].state = 0;     // 未訪問
    }

    vert[start.val].state = 1;   // 訪問済み
    vert[start.val].pred = -1;   // 親ノードなし
    que.push(start);   // 開始ノードを挿入

    while(!que.empty()) {
        // キューから取り出す
        u = que.front();
        que.pop();

        for(i = 0; i<NODE; i++) {
            if(resGraph[u.val][i] > 0 && vert[i].state == 0) {
                que.push(vert[i]);
                vert[i].pred = u.val;
                vert[i].state = 1;
            }
        }
    }
    return (vert[sink.val].state == 1);
}

// フォード・ファルカーソンの本体
int fordFulkerson(node *vert, node source, node sink) {
    int maxFlow = 0;
    int u, v;

    for(int i = 0; i<NODE; i++) {
        for(int j = 0; j<NODE; j++) {
            resGraph[i][j] = graph[i][j];  // 初期状態では残余グラフ＝元のグラフ
        }
    }

    while(bfs(vert, source, sink)) {   // BFSで増加パスを探す
        int pathFlow = 999;// 無限大の代用
        for(v = sink.val; v != source.val; v=vert[v].pred) {
            u = vert[v].pred;
            pathFlow = minimum(pathFlow, resGraph[u][v]);
        }

        for(v = sink.val; v != source.val; v=vert[v].pred) {
            u = vert[v].pred;
            resGraph[u][v] -= pathFlow;  // 辺の残余容量を更新
            resGraph[v][u] += pathFlow;  // 逆辺の残余容量を更新
        }

        maxFlow += pathFlow;
    }
    return maxFlow;    // 全体の最大フロー
}

int main() {
    node vertices[NODE];
    node source, sink;

    for(int i = 0; i<NODE; i++) {
        vertices[i].val = i;
    }

    source.val = 0;
    sink.val = 5;
    int maxFlow = fordFulkerson(vertices, source, sink);
    cout << "Maximum flow is: " << maxFlow << endl;
}

実行結果

Maximum flow is: 19

まとめ

フォード・ファルカーソン法は、「BFSで増加パスを1本見つける → パス上の最小容量分だけフローを流す → 残余グラフを更新する」という処理を、増加パスが存在しなくなるまで繰り返すことで最大流を求めます。計算量は O(E × 最大フロー値) となり、辺の数とフロー値に依存します。なお、常に最短の増加パスを選ぶように改良したものが「エドモンズ・カープ（Edmonds-Karp）アルゴリズム」であり、こちらは O(VE²) の計算量で動作することが保証されています。