有向非巡回グラフ(DAG)の最短経路をトポロジカルソートで効率的に求める方法

重み付き有向非巡回グラフ(DAG:Directed Acyclic Graph)と、始点となる頂点が与えられます。ここでの課題は、始点ノードからグラフ内の他のすべての頂点への最短距離を求めることです。

最短距離を求めるアルゴリズムとしては、負の重みを含むグラフに対してはベルマン・フォード法、正の重みのみのグラフに対してはダイクストラ法が広く知られています。しかし、対象が有向非巡回グラフ(DAG)である場合は、トポロジカルソート(位相整列)のテクニックを活用することで、これらの汎用アルゴリズムよりも低い計算量で最短経路を求めることができます。

入力と出力

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

出力:始点頂点1からの最短距離
Infinity 0 2 6 5 3

アルゴリズム

topoSort(u, visited, stack)

入力: 始点ノード u、訪問状況を記録する visited リスト、スタック
出力: 頂点をトポロジカルな順序に並べる

Begin
    u を訪問済みとしてマークする
    u に接続しているすべての頂点 v について
        v が未訪問であれば
            topoSort(v, visited, stack) を再帰的に呼び出す
    u をスタックにプッシュする
End

shortestPath(start)

入力: 始点ノード
出力: 始点から各頂点への最短距離のリスト

Begin
    最初にすべてのノードを未訪問に初期化する
    グラフ内の各ノード i について
        i が未訪問であれば
            topoSort(i, visited, stack) を呼び出す

    すべての頂点の距離を ∞ に設定する
    dist[start] := 0
    スタックが空になるまで繰り返す
        スタックから要素を取り出し nextVert とする
        dist[nextVert] ≠ ∞ であれば
            nextVert に隣接する各頂点 v について
                cost[nextVert, v] ≠ ∞ であれば
                    dist[v] > dist[nextVert] + cost[nextVert, v] であれば
                        dist[v] := dist[nextVert] + cost[nextVert, v]

    グラフ内のすべての頂点 i について
        dist[i] = ∞ であれば「Infinity」を表示
        それ以外は dist[i] を表示
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);                    // 頂点uをスタックにプッシュ
}

// トポロジカル順に従って最短距離を緩和
void shortestPath(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;              // 初期状態では全距離を無限大に設定
    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] << " ";
}

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

出力結果

Shortest Distance From Source Vertex 1
Infinity 0 2 6 5 3

この結果から、頂点0は始点(頂点1)から到達できないため距離が無限大(Infinity)となり、残りの頂点については最短距離が正しく求まっていることが分かります。

計算量

トポロジカルソートは深さ優先探索に基づくため O(V+E)、その後の距離の緩和処理でも各頂点と各辺をそれぞれ1回ずつ処理するだけでよいため、全体の計算量は O(V+E) となります。これは、ダイクストラ法(O(V²)、二分ヒープ使用時は O((V+E) log V))やベルマン・フォード法(O(V·E))と比べて非常に効率的です。さらに、DAGには閉路が存在しないため、負の重みを持つ辺が含まれていても正しく動作する点も大きな利点です。