【C++】Ford-Fulkerson法でネットワークフロー問題（最大流）を実装する方法

これは、Ford-Fulkerson（フォード・ファルカーソン）アルゴリズムを用いてネットワークフロー問題を実装したC++プログラムの解説記事です。BFS（幅優先探索）による増加パスの探索を繰り返すことで、ソース（始点）からシンク（終点）へ流せる最大流量を求めます。

ネットワークフロー問題とは

ネットワークフロー問題は、各辺に容量（キャパシティ）が設定された有向グラフにおいて、始点から終点へ送れる流量の最大値を求める古典的な最適化問題です。物流網・通信網・配水管網などの設計や解析など、幅広い分野で応用されています。

この問題を解く代表的な手法がFord-Fulkerson法です。「残余グラフ上でまだ流量を増やせる経路（増加パス）を探し、見つかる限り流量を積み増していく」という考え方に基づいています。

アルゴリズムの流れ

Begin
    関数 bfs()：残余グラフ内にソース s からシンク t への経路が存在する場合、
    グラフに追加の流量を流せることが分かるため true を返す。
End

Begin
    関数 fordFulkerson()：与えられたグラフの最大流量を返す。
    A) 流量を 0 で初期化する。
    B) ソースからシンクへの増加パスが存在する間、そのパスの流量を合計に加算する。
    C) 最大流量を返す。
End

実装のポイント

• bfs()：キューを使った幅優先探索で、残余容量が正の辺のみをたどってシンクへ到達できるかを判定し、経路復元用に親頂点を記録します。
• fordFulkerson()：BFSで見つかった増加パス上の最小残余容量（ボトルネック）を流量として加算し、順方向の容量を減らして逆方向の容量を増やすことで残余グラフを更新します。
• 計算量：BFSで増加パスを探索するこの実装は Edmonds-Karp 法と呼ばれ、時間計算量は O(V·E²) です。

サンプルコード

#include <iostream>
#include <climits>
#include <cstring>
#include <queue>
#define n 7
using namespace std;

bool bfs(int g[n][n], int s, int t, int par[])
{
    bool visit[n];
    memset(visit, 0, sizeof(visit));
    queue <int> q;
    q.push(s);
    visit[s] = true;
    par[s] = -1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int v = 0; v < n; v++)
        {
            if (visit[v] == false && g[u][v] > 0)
            {
                q.push(v);
                par[v] = u;
                visit[v] = true;
            }
        }
    }
    return (visit[t] == true);
}

int fordFulkerson(int G[n][n], int s, int t)
{
    int u, v;
    int g[n][n];
    for (u = 0; u < n; u++)
    {
        for (v = 0; v < n; v++)
            g[u][v] = G[u][v];
    }
    int par[n];
    int max_flow = 0;
    while (bfs(g, s, t, par))
    {
        int path_flow = INT_MAX;
        for (v = t; v != s; v = par[v])
        {
            u = par[v];
            path_flow = min(path_flow, g[u][v]);
        }
        for (v = t; v != s; v = par[v])
        {
            u = par[v];
            g[u][v] -= path_flow;
            g[v][u] += path_flow;
        }
        max_flow += path_flow;
    }
    return max_flow;
}

int main()
{
    int g[n][n] = {{0, 6, 7, 1},
                   {0, 0, 4, 2},
                   {0, 5, 0, 0},
                   {0, 0, 19, 12},
                   {0, 0, 0, 17},
                   {0, 0, 0, 0}};
    cout << "The maximum possible flow is " << fordFulkerson(g, 0, 3);
    return 0;
}

出力結果

The maximum possible flow is 3

この例では、頂点0（ソース）から頂点3（シンク）へ流せる最大流量が 3 であることが分かります。直接辺 0→3（容量1）と、経路 0→1→3（容量2）を合わせた流量が最大となっています。