有向非巡回グラフ(DAG)における最長パスの求め方

重み付き有向非巡回グラフ(DAG)と、始点となる頂点が1つ与えられます。ここでの目的は、開始ノードからグラフ上の他のすべての頂点までの最長距離を求めることです。

この問題はトポロジカルソートを利用することで効率的に解くことができます。まずグラフのノードをトポロジカルソートで並べ替え、その結果をスタックに格納します。その後、スタックから頂点を取り出すたびに、各頂点への最長距離を順次更新していきます。

DAGには閉路(サイクル)が存在しないため、負の重みを持つ辺が含まれていても、パスの距離が無限に増大することはありません。そのため、ダイクストラ法やベルマン・フォード法を用いなくても、トポロジカルソートを活用すれば非常にシンプルな手順で最長パスを求められます。

入力と出力

入力:
グラフのコスト行列
0  5  3 -∞ -∞ -∞
-∞ 0  2  6 -∞ -∞
-∞ -∞ 0  7  4  2
-∞ -∞ -∞ 0 -1  1
-∞ -∞ -∞ -∞ 0 -2
-∞ -∞ -∞ -∞ -∞ 0

出力:
始点頂点1からの最長距離
Infinity 0 2 9 8 10

アルゴリズム

topoSort(u, visited, stack)

入力: 開始ノード u、訪問済み頂点を記録するリスト visited、スタック。

出力: ノードをトポロジカルな順序に並べ替えた結果。

Begin
   mark u as visited
   for all vertex v, which is connected with u, do
      if v is not visited, then
         topoSort(v, visited, stack)
   done
   push u into the stack
End

longestPath(start)

入力: 開始ノード。

出力: 開始ノードからすべての頂点への最長距離のリスト。

Begin
   initially make all nodes as unvisited
   for each node i, in the graph, do
      if i is not visited, then
         topoSort(i, visited, stack)
   done

   make distance of all vertices as -∞
   dist[start] := 0
   while stack is not empty, do
      pop stack item and take into nextVert
      if dist[nextVert] ≠ -∞, then
         for each vertices v, which is adjacent with nextVert, do
            if cost[nextVert, v] ≠ -∞, then
               if dist[v] < dist[nextVert] + cost[nextVert, v], then
                  dist[v] := dist[nextVert] + cost[nextVert, v]
         done
      done
   done

   for all vertices i in the graph, do
      if dist[i] = -∞, then
         display Infinity
      else
         display dist[i]
   done
End

C++による実装例

#include<iostream>
#include<stack>
#define NODE 6
#define INF -9999
using namespace std;

int cost[NODE][NODE] = {
   {0, 5, 3, INF, INF, INF},
   {INF, 0, 2, 6, INF, INF},
   {INF, INF, 0, 7, 4, 2},
   {INF, INF, INF, 0, -1, 1},
   {INF, INF, INF, INF, 0, -2},
   {INF, INF, INF, INF, INF, 0}
};

void topoSort(int u, bool visited[], stack<int>& stk) {
   visited[u] = true;      // 頂点uを訪問済みとして記録

   for(int v = 0; v<NODE; v++) {
      if(cost[u][v]) {     // uに隣接するすべての頂点vについて
         if(!visited[v])
            topoSort(v, visited, stk);
      }
   }

   stk.push(u);            // 開始頂点をスタックに積む
}

void longestPath(int start) {
   stack<int> stk;
   int dist[NODE];
   bool vis[NODE];

   for(int i = 0; i<NODE; i++)
      vis[i] = false;      // 最初にすべてのノードを未訪問にする

   for(int i = 0; i<NODE; i++)   // 各頂点に対してトポロジカルソートを実行
      if(!vis[i])
         topoSort(i, vis, stk);

   for(int i = 0; i<NODE; i++)
      dist[i] = INF;       // 初期状態ではすべての距離を無限大(-INF)に設定
   dist[start] = 0;        // 始点の距離は0

   while(!stk.empty()) {   // スタックが空でない間、トポロジカル順に処理
      int nextVert = stk.top(); stk.pop();

      if(dist[nextVert] != INF) {
         for(int v = 0; v<NODE; v++) {
            if(cost[nextVert][v] && cost[nextVert][v] != INF) {
               if(dist[v] < dist[nextVert] + cost[nextVert][v])
                  dist[v] = dist[nextVert] + cost[nextVert][v];
            }
         }
      }
   }

   for(int i = 0; i<NODE; i++)
      (dist[i] == INF) ? cout << "Infinity " : cout << dist[i] << " ";
}

main() {
   int start = 1;
   cout << "Longest Distance From Source Vertex " << start << endl;
   longestPath(start);
}

この実装では、再帰的なDFSによってトポロジカルソートを行い、その結果得られるスタックの順序(トポロジカル順)に従って距離を緩和していく点がポイントです。始点から到達できない頂点の距離は -∞ のまま残るため、出力時には「Infinity」と表示されます。

計算量

トポロジカルソート自体は O(V+E) で実行でき、その後の距離更新処理も隣接リスト表現であれば O(V+E) で完了します。本記事の実装例ではコスト行列(隣接行列)を使用しているため、全体の計算量は O(V²) となります。

出力

Longest Distance From Source Vertex 1
Infinity 0 2 9 8 10

始点である頂点1自身の距離は 0、そこから直接到達できない頂点0は「Infinity」と表示され、それ以外の頂点にはそれぞれの最長距離が出力されています。