C++でグラフに長さkを超える単純パスが存在するか判定するアルゴリズム

概念

重み付きグラフ、グラフ内の始点となる頂点、そして数値k(kは始点から終点までのパスの長さを表します)が与えられたとき、与えられた始点から始まり、任意の他の頂点(終点)で終わる単純パス(閉路を含まないパス)が存在するかどうかを判定することが課題です。以下のグラフを使って説明します。

入力例1

始点 s = 0, k = 64

出力

True

この場合、0 -> 7 -> 1 -> 2 -> 8 -> 6 -> 5 -> 3 -> 4 という合計距離68の単純パスが存在し、64を超えているためtrueとなります。

入力例2

始点 s = 0, k = 70

出力

False

一方、このグラフにおける最長の単純パスの距離は69(0 -> 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8)であるため、69より大きい値が入力された場合はfalseを出力すべきです。

解法の考え方

まず注意すべき重要なポイントとして、単純にBFS(幅優先探索)やDFS(深さ優先探索)を行い、毎ステップで最も重みの大きい辺を選択する貪欲な手法では正しく判定できません。その理由は、現時点では短い辺であっても、その先につながる重みの大きな辺を経由することで、結果的により長いパスが得られる可能性があるためです。

そこで用いるのがバックトラッキングです。与えられた始点から探索を開始し、現在の頂点から伸びるすべての経路を順に辿ります。この際、始点からの現在の累積距離を管理します。距離がkを超えた時点でtrueを返し、ある経路を辿っても距離がkを超えなかった場合は、バックトラックして別の経路を試します。

次に問題になるのは、パスが単純であること(閉路に入らないこと)をどう保証するかです。この解決策として、現在のパス上に含まれる頂点を配列で記録しておきます。頂点をパスに追加する際に、その頂点が既にパスに存在するかどうかを確認し、存在する場合はその辺を無視します。

計算量について

この手法はすべての単純パスを列挙するため、最悪計算量は頂点数をVとするとO(V!)程度に達します。そのため小規模なグラフに適した手法であり、大規模なグラフに対しては動的計画法(ビットDP)など別のアプローチを検討する必要があります。

C++実装例

// 重みがkより大きい単純パスが存在するかどうかを調べるプログラム
#include<bits/stdc++.h>
using namespace std;
// iPair ==> 整数のペア
typedef pair<int, int> iPair;
// このクラスは、隣接リスト表現を用いて無向重み付きグラフを表す
class Graph{
    int V1; // 頂点の数
    // 重み付きグラフでは、各辺について「頂点と重みのペア」を格納する必要がある
    list< pair<int, int>> *adj1;
    bool pathMoreThanKUtil(int src1, int k, vector<bool>&path1);
public:
    Graph(int V1); // コンストラクタ
    // グラフに辺を追加する関数
    void addEdge(int u1, int v1, int w1);
    bool pathMoreThanK(int src1, int k);
};
// グラフに長さkより大きいパスが存在する場合にtrueを返す
bool Graph::pathMoreThanK(int src1, int k){
    // パス情報を保持する配列を作成(初期状態では何も含まれていない)
    vector<bool> path1(V1, false);
    // 始点となる頂点をパスに追加
    path1[src1] = 1;
    return pathMoreThanKUtil(src1, k, path1);
}
// 始点srcから各頂点への経路を再帰的に探索する補助関数
bool Graph::pathMoreThanKUtil(int src1, int k, vector<bool>&path1){
    // kが0以下であればtrueを返す
    if (k <= 0)
        return true;
    // 始点srcに隣接するすべての頂点を取得し、
    // srcからのすべての経路を再帰的に探索する
    list<iPair>::iterator i;
    for (i = adj1[src1].begin(); i != adj1[src1].end(); ++i){
        // 隣接する頂点と辺の重みを取得
        int v1 = (*i).first;
        int w1 = (*i).second;
        // 頂点vがすでにパスに含まれている場合、
        // 閉路になるためこの辺は無視する
        if (path1[v1] == true)
            continue;
        // 辺の重みがk以上であればtrueを返す
        if (w1 >= k)
            return true;
        // それ以外の場合、この頂点をパスに追加
        path1[v1] = true;
        // この隣接頂点から先に、kより長いパスが
        // 存在する場合はtrueを返す
        if (pathMoreThanKUtil(v1, k-w1, path1))
            return true;
        // バックトラック
        path1[v1] = false;
    }
    // どの隣接頂点からもより長いパスが見つからなければfalseを返す
    return false;
}
// 隣接リスト用のメモリを確保するコンストラクタ
Graph::Graph(int V1){
    this->V1 = V1;
    adj1 = new list<iPair> [V1];
}
// 辺(u, v)とその重みwを追加するユーティリティ関数
void Graph::addEdge(int u1, int v1, int w1){
    adj1[u1].push_back(make_pair(v1, w1));
    adj1[v1].push_back(make_pair(u1, w1));
}
// Graphクラスのメソッドをテストするドライバプログラム
int main(){
    // 上の図に示したグラフを作成する
    int V1 = 9;
    Graph g(V1);
    // 図に示したグラフを構築
    g.addEdge(0, 1, 5);
    g.addEdge(0, 7, 9);
    g.addEdge(1, 2, 9);
    g.addEdge(1, 7, 12);
    g.addEdge(2, 3, 8);
    g.addEdge(2, 8, 3);
    g.addEdge(2, 5, 10);
    g.addEdge(3, 4, 10);
    g.addEdge(3, 5, 15);
    g.addEdge(4, 5, 11);
    g.addEdge(5, 6, 3);
    g.addEdge(6, 7, 2);
    g.addEdge(6, 8, 7);
    g.addEdge(7, 8, 8);
    int src1 = 0;
    int k = 70;
    g.pathMoreThanK(src1, k)? cout << "Yes\n" :
    cout << "No\n";
    k = 68;
    g.pathMoreThanK(src1, k)? cout << "Yes\n" :
    cout << "No\n";
    return 0;
}

出力

No
Yes

k=70の場合は長さ70を超える単純パスが存在しないため「No」、k=68の場合は距離68の単純パスが存在するため「Yes」が出力されます。

まとめ

この記事では、重み付きグラフにおいて始点から長さkを超える単純パスが存在するかどうかを判定する問題を取り上げました。貪欲に最長の辺を選ぶだけでは最適解が得られないことを確認し、バックトラッキングを用いてすべての単純パスを体系的に探索する実装方法を紹介しました。閉路の検出には、訪問済み頂点を記録する配列を活用するのがポイントです。