【C++】2つの頂点間の辺素パス（エッジディスジョイントパス）の最大数を求める方法

この記事では、C++を使って、グラフ上の2つの頂点（始点と終点）の間に存在する辺素パスの最大数を求めるプログラムを紹介します。辺素パスとは、互いに同じ辺（エッジ）を1つも共有しない複数のパスのことであり、その最大本数は2頂点間の最大フロー（最大流）と一致するという重要な性質を持っています。

アルゴリズム

開始
　　関数 bfs()：残余グラフ上で始点 s から終点 t への経路が
　　存在する場合に true を返す。
　　（これはグラフにまだ流せるフローが残っていることを示す）
終了
開始
　　関数 findDisPath()：与えられたグラフの最大フローを返す。
　　A) フローを 0 に初期化する。
　　B) 始点から終点への増加パスが存在する限り、その流量をフローに加算する。
　　C) フローを返す。
終了

C++による実装例

#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 findDisPath(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}};
    int s = 0, d = 3;
    cout << "There exist maximum " << findDisPath(g, s, d)
         << " edge-disjoint paths from " << s << " to " << d;
    return 0;
}

実行結果

There exist maximum 3 edge-disjoint paths from 0 to 3

この出力は、「頂点 0 から頂点 3 への辺素パスは最大 3 本存在する」という意味です。

プログラムの仕組み

• bfs()： 残余グラフに対して幅優先探索（BFS）を行い、始点から終点へまだ流量を増やせる経路（増加パス）が存在するかどうかを判定します。キューを使って探索を進めながら、親配列 par[] に各頂点の直前の頂点を記録していきます。
• findDisPath()： 元のグラフをコピーした残余グラフ上で、BFSによる増加パスの探索を繰り返します。パスが見つかるたびに、そのパス上の最小容量（ボトルネック）だけ流れを進め、順方向の容量を減らし、逆方向の容量を増やします。
• 最大フロー＝辺素パスの最大数： 増加パスがこれ以上見つからなくなった時点での累積フローが、そのまま2頂点間の辺素パスの最大本数となります。

この手法はフォード・ファルカーソンのアルゴリズムをベースにしており、特にBFSで最短の増加パスを優先的に選ぶ方式は「エドモンズ・カープ法」として知られています。ネットワーク設計や通信経路の冗長性評価など、実用的な場面でも応用される考え方なので、ぜひ理解しておきましょう。