【Python】ノードを重複させずにDAGの最長パスの長さを求めるプログラム

DAGの最長パス問題とは

隣接リスト形式で表された有向非巡回グラフ(DAG: Directed Acyclic Graph)が与えられたとき、同じノードを2度通らずに辿れる最長パスの長さを求める問題を考えます。

例として、次のようなグラフを想定してみましょう。

この場合、パス「0 → 1 → 3 → 4 → 2」が最長となるため、出力は 4 になります。

解法のアプローチ:DFSとメモ化の組み合わせ

この問題は、深さ優先探索(DFS)にメモ化(結果のキャッシュ)を組み合わせることで効率的に解けます。各ノードから始まる最長パスの長さを一度計算したら結果を保存し、同じ計算を繰り返さないのがポイントです。

アルゴリズムの手順

• 答えを格納する変数 ans を 0 で初期化する
• n をグラフのノード数とする
• サイズ n のリスト table を作成し、すべて -1 で埋める(-1 は「未計算」の目印)
• 関数 dfs(u) を次のように定義する:
  • table[u] が -1 でなければ、計算済みなのでその値をそのまま返す
  • p_len を 0 で初期化する
  • graph[u] 内の各頂点 v について、p_len = max(p_len, 1 + dfs(v)) を実行する
  • table[u] = p_len として結果をキャッシュし、p_len を返す
• メイン処理では、すべてのノード i(0 〜 n-1)に対して ans = max(ans, dfs(i)) を実行する
• 最後に ans を返す

Pythonでの実装例

以下のコードで実際の動きを確認してみましょう。

class Solution:
    def solve(self, graph):
        ans = 0
        n = len(graph)
        table = [-1] * n

        def dfs(u):
            if table[u] != -1:
                return table[u]
            p_len = 0
            for v in graph[u]:
                p_len = max(p_len, 1 + dfs(v))
            table[u] = p_len
            return p_len

        for i in range(n):
            ans = max(ans, dfs(i))
        return ans

ob = Solution()
graph = [
    [1, 2],
    [3, 4],
    [],
    [4],
    [2],
]
print(ob.solve(graph))

入力

graph = [[1, 2],[3, 4],[],[4],[2]]

出力

4

計算量のポイント

メモ化により、各ノードの最長パスは一度だけ計算されるため、時間計算量は O(V + E)(Vは頂点数、Eは辺数)、空間計算量は O(V) となります。また、DAGには閉路が存在しないため、この再帰的なアプローチでも無限ループに陥る心配はありません。グラフが大きくなっても安定して動作する、実用的なアルゴリズムといえます。