C++によるエドモンズ・カープ（Edmonds-Karp）アルゴリズムの実装：最大流を計算するプログラム

本記事では、C++を用いてエドモンズ・カープ（Edmonds-Karp）アルゴリズムを実装し、グラフの始点（ソース）から終点（シンク）までの最大流（Maximum Flow）を計算する方法を解説します。

アルゴリズムの概要

エドモンズ・カープ法は、フォード・ファルカーソン法を改良したアルゴリズムで、増加経路（Augmenting Path）の探索に幅優先探索（BFS）を採用している点が特徴です。常に最短の増加経路から流量を確定していくため、計算量は O(V・E²) に抑えられます。

Begin
    function edmondsKarp() :
        流量を 0 に初期化する。
        ソースからシンクへの増加経路が存在する間、その経路の流量を加算し続ける。
        最終的な合計流量を返す。
End

処理の流れ

1. BFSによって、残余容量が正の辺のみを通ってシンクに到達できる最短の増加経路を見つける。
2. その経路における最小の残余容量（ボトルネック容量）を、今回追加する流量として決定する。
3. 順方向の流量を加算し、逆方向の流量を減算することで、フロー全体を更新する。
4. 増加経路が見つからなくなった時点で、累積した流量が最大流となる。

サンプルコード

#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
int c[10][10];              // 各辺の容量
int flowPassed[10][10];     // すでに流した流量
vector<int> g[10];          // グラフの隣接リスト
int parList[10];            // 経路復元用の親ノード配列
int currentPathC[10];       // 現在の経路における最小残余容量
int bfs(int sNode, int eNode)// 幅優先探索
{
    memset(parList, -1, sizeof(parList));
    memset(currentPathC, 0, sizeof(currentPathC));
    queue<int> q;// キューの宣言
    q.push(sNode);
    parList[sNode] = -1;// 始点の親を初期化
    currentPathC[sNode] = 999;// 始点の残余容量を十分大きな値で初期化
    while(!q.empty())// キューが空でない間繰り返す
    {
        int currNode = q.front();
        q.pop();
        for(int i=0; i<g[currNode].size(); i++)
        {
            int to = g[currNode][i];
            if(parList[to] == -1)
            {
                if(c[currNode][to] - flowPassed[currNode][to] > 0)
                {
                    parList[to] = currNode;
                    currentPathC[to] = min(currentPathC[currNode],
                    c[currNode][to] - flowPassed[currNode][to]);
                    if(to == eNode)
                    {
                        return currentPathC[eNode];
                    }
                    q.push(to);
                }
            }
        }
    }
    return 0;
}
int edmondsKarp(int sNode, int eNode)
{
    int maxFlow = 0;
    while(true)
    {
        int flow = bfs(sNode, eNode);
        if (flow == 0)
        {
            break;
        }
        maxFlow += flow;
        int currNode = eNode;
        while(currNode != sNode)
        {
            int prevNode = parList[currNode];
            flowPassed[prevNode][currNode] += flow;
            flowPassed[currNode][prevNode] -= flow;
            currNode = prevNode;
        }
    }
return maxFlow;
}
int main()
{
    int nodCount, edCount;
    cout<<"enter the number of nodes and edges\n";
    cin>>nodCount>>edCount;
    int source, sink;
    cout<<"enter the source and sink\n";
    cin>>source>>sink;
    for(int ed = 0; ed < edCount; ed++)
    {
        cout<<"enter the start and end vertex along with capacity\n";
        int from, to, cap;
        cin>>from>>to>>cap;
        c[from][to] = cap;
        g[from].push_back(to);
        g[to].push_back(from);
    }
    int maxFlow = edmondsKarp(source, sink);
    cout<<endl<<endl<<"Max Flow is:"<<maxFlow<<endl;
}

出力結果

以下は、6頂点・7辺のグラフに対して、始点「0」、終点「4」を指定して実行した例です。各辺については、始点・終点の頂点番号と容量を順に入力しています。

enter the number of nodes and edges
6
7
enter the source and sink
0
4
enter the start and end vertex along with capacity
0
1
14
enter the start and end vertex along with capacity
2
4
10
enter the start and end vertex along with capacity
6
7
9
enter the start and end vertex along with capacity
5
2
10
enter the start and end vertex along with capacity
1
4
12
enter the start and end vertex along with capacity
2
0
15
enter the start and end vertex along with capacity
5
3
15
Max Flow is:12

この入力例では、始点0から終点4まで流せる最大流量が 12 であると計算されています。エドモンズ・カープ法を使うことで、ネットワークフロー問題を効率よく解くことができます。