【Python】グラフの始点から長さk以上の単純パスが存在するか判定する方法

グラフと始点となる頂点、そして数値 k が与えられたとします。ここで k は「始点から目的地までの経路の長さ」を表します。このとき、始点から出発し、任意の頂点（目的地）で終わる、閉路（サイクル）を含まない単純パスが存在するかどうかを判定するのが本記事の目的です。

問題の概要

以下のような重み付き無向グラフを考えてみましょう。

例として、始点 = 0、k = 64 という入力が与えられた場合を考えます。この場合の出力は True になります。なぜなら、「0 → 7 → 1 → 2 → 8 → 6 → 5 → 3 → 4」という単純パスが存在し、その総距離は 68 となり、64 を超えているためです。

解法のアプローチ

この問題はバックトラッキング（深さ優先探索）を用いて解くことができます。手順は以下の通りです。

• 頂点数 × 頂点数の隣接リスト adj を定義し、各辺のコストを格納する。
• 関数 solve(source, k, path) を定義する。
• k ≤ 0 の場合、必要な長さに達したので True を返す。
• i = 0 と初期化し、i が adj[source] の要素数と等しくなるまで以下を繰り返す。
  • v := adj[source][i][0]（隣接頂点）、w := adj[source][i][1]（辺の重み）を取得し、i を 1 増やす。
  • path[v] が True（すでに訪問済み）の場合は次の反復へスキップする。
  • w ≥ k の場合、この辺だけで残りの距離を満たせるので True を返す。
  • path[v] := True として訪問済みにマークする。
  • solve(v, k − w, path) が True を返せば、そのまま True を返す。
  • そうでなければ path[v] := False に戻して（バックトラック）次の候補を試す。
• すべての候補を試しても成功しなければ False を返す。
• メイン処理では、頂点数と同じサイズのリスト path を False で初期化し、path[source] を True に設定してから solve(source, k, path) を呼び出す。

実装例

それでは、実際の Python コードを見てみましょう。

class Graph:
    def __init__(self, nodes):
        self.nodes = nodes
        self.adj = [[] for i in range(nodes)]

    def insert_edge(self, u, v, w):
        self.adj[u].append([v, w])
        self.adj[v].append([u, w])

    def solve(self, source, k, path):
        if (k <= 0):
            return True
        i = 0
        while i != len(self.adj[source]):
            v = self.adj[source][i][0]
            w = self.adj[source][i][1]
            i += 1
            if (path[v] == True):
                continue
            if (w >= k):
                return True
            path[v] = True
            if (self.solve(v, k - w, path)):
                return True
            path[v] = False
        return False

    def is_there_any_path(self, source, k):
        path = [False] * self.nodes
        path[source] = 1
        return self.solve(source, k, path)

nodes = 9
g = Graph(nodes)
g.insert_edge(0, 1, 5)
g.insert_edge(0, 7, 9)
g.insert_edge(1, 2, 9)
g.insert_edge(1, 7, 12)
g.insert_edge(2, 3, 8)
g.insert_edge(2, 8, 3)
g.insert_edge(2, 5, 5)
g.insert_edge(3, 4, 10)
g.insert_edge(3, 5, 15)
g.insert_edge(4, 5, 11)
g.insert_edge(5, 6, 3)
g.insert_edge(6, 7, 2)
g.insert_edge(6, 8, 7)
g.insert_edge(7, 8, 8)

source = 0
k = 64
print(g.is_there_any_path(source, k))

入力

nodes = 9
g = Graph(nodes)
g.insert_edge(0, 1, 5)
g.insert_edge(0, 7, 9)
g.insert_edge(1, 2, 9)
g.insert_edge(1, 7, 12)
g.insert_edge(2, 3, 8)
g.insert_edge(2, 8, 3)
g.insert_edge(2, 5, 5)
g.insert_edge(3, 4, 10)
g.insert_edge(3, 5, 15)
g.insert_edge(4, 5, 11)
g.insert_edge(5, 6, 3)
g.insert_edge(6, 7, 2)
g.insert_edge(6, 8, 7)
g.insert_edge(7, 8, 8)
source = 0
k = 64

出力

True

まとめ

このアルゴリズムでは、訪問済み頂点を記録しながら再帰的に探索を行い、行き詰まったらバックトラックすることで、条件を満たす単純パスの有無を効率的に判定できます。計算量は最悪情况下 O(n!) となり得ますが、小規模なグラフや特定の条件下では十分実用的です。グラフ探索やバックトラッキングの理解を深める良い題材と言えるでしょう。