隣接リスト表現のグラフにおけるダイクストラ法の実装と解説

隣接リスト形式で表現されたグラフ G(V, E) と始点（ソース）頂点が与えられているとき、ダイクストラ法を用いることで、始点からグラフ内の他のすべての頂点への最短経路を求めることができます。

この問題を解くには、次の2つのリストを使用します。

• 確定済みリスト： 最短経路木としてすでに確定した頂点を格納します。
• 未確定リスト： まだ確定していない頂点を保持します。

アルゴリズムの各ステップでは、未確定の頂点の中から始点からの距離が最小となる頂点を選び出し、確定済みリストへ移動させます。

また、各頂点の先行ノード（直前のノード）を記録するリストも用意します。この先行ノードを逆にたどることで、始点から目的地までの実際の経路を復元することが可能です。

グラフを隣接リストで表現した場合、ダイクストラ法の計算量は O(E log V) となります。ここで E は辺の数、V は頂点の数です。

入力と出力

Input:
各辺のコストを持つグラフの隣接リスト

Output:
0 to 1, Cost: 3 Previous: 0
0 to 2, Cost: 5 Previous: 1
0 to 3, Cost: 4 Previous: 1
0 to 4, Cost: 6 Previous: 3
0 to 5, Cost: 7 Previous: 2
0 to 6, Cost: 7 Previous: 4

アルゴリズム

dijkstraShortestPath(g : Graph, dist, prev, start : node)

入力 − グラフ g、各頂点までの距離を格納する dist リスト、先行ノードを記録する prev リスト、始点頂点。

出力 − 始点から他のすべての頂点への最短経路。

Begin
    for all vertices u in (V - start) do
        dist[u] := ∞
        prev[u] := φ
    done

    set dist[start] = 0 and prev[start] := φ;

    for all node u in V do
        insert u into queue ‘Q’.
    done

    while Q is not empty do
        u := minimum element from Queue
        delete u from Q
        insert u into set S

        for each node v adjacent with node u do
            if dist[u]+cost(v) < dist[v] then
                dist[v] := dist[u]+cost(v)
                prev[v] := u
        done
    done
End

C++による実装例

#include<iostream>
#include<set>
#include<list>
#include<algorithm>
using namespace std;

typedef struct nodes {
    int dest;
    int cost;
}node;

class Graph {
    int n;
    list<node> *adjList;
    private:
        void showList(int src, list<node> lt) {
            list<node> :: iterator i;
            node tempNode;

            for(i = lt.begin(); i != lt.end(); i++) {
                tempNode = *i;
                cout << "(" << src << ")---("<<tempNode.dest << "|"<<tempNode.cost<<") ";
            }
            cout << endl;
        }
    public:
        Graph() {
            n = 0;
        }

        Graph(int nodeCount) {
            n = nodeCount;
            adjList = new list<node>[n];
        }

        void addEdge(int source, int dest, int cost) {
            node newNode;
            newNode.dest = dest;
            newNode.cost = cost;
            adjList[source].push_back(newNode);
        }

        void displayEdges() {
            for(int i = 0; i<n; i++) {
                list<node> tempList = adjList[i];
                showList(i, tempList);
            }
        }

        friend void dijkstra(Graph g, int *dist, int *prev, int start);
};

void dijkstra(Graph g, int *dist, int *prev, int start) {
    int n = g.n;

    for(int u = 0; u<n; u++) {
        dist[u] = 9999;   //無限大として扱う
        prev[u] = -1;     //先行ノードは未定義
    }

    dist[start] = 0;      //始点までの距離は0
    set<int> S;           //空の集合Sを作成
    list<int> Q;

    for(int u = 0; u<n; u++) {
        Q.push_back(u);   //全ノードをキューに追加
    }

    while(!Q.empty()) {
        list<int> :: iterator i;
        i = min_element(Q.begin(), Q.end());
        int u = *i;       //キュー内の最小要素を取得
        Q.remove(u);
        S.insert(u);      //uを集合Sに追加
        list<node> :: iterator it;

        for(it = g.adjList[u].begin(); it != g.adjList[u].end();it++) {
            if((dist[u]+(it->cost)) < dist[it->dest]) { //辺(u,v)の緩和処理
                dist[it->dest] = (dist[u]+(it->cost));
                prev[it->dest] = u;
            }
        }
    }
}

main() {
    int n = 7;
    Graph g(n);
    int dist[n], prev[n];
    int start = 0;

    g.addEdge(0, 1, 3);
    g.addEdge(0, 2, 6);
    g.addEdge(1, 0, 3);
    g.addEdge(1, 2, 2);
    g.addEdge(1, 3, 1);
    g.addEdge(2, 1, 6);
    g.addEdge(2, 1, 2);
    g.addEdge(2, 3, 1);
    g.addEdge(2, 4, 4);

    g.addEdge(2, 5, 2);
    g.addEdge(3, 1, 1);
    g.addEdge(3, 2, 1);
    g.addEdge(3, 4, 2);
    g.addEdge(3, 6, 4);
    g.addEdge(4, 2, 4);
    g.addEdge(4, 3, 2);
    g.addEdge(4, 5, 2);
    g.addEdge(4, 6, 1);
    g.addEdge(5, 2, 2);
    g.addEdge(5, 4, 2);
    g.addEdge(5, 6, 1);
    g.addEdge(6, 3, 4);
    g.addEdge(6, 4, 1);
    g.addEdge(6, 5, 1);

    dijkstra(g, dist, prev, start);

    for(int i = 0; i<n; i++)
        if(i != start)
            cout<<start<<" to "<<i<<", Cost: "<<dist[i]<<" Previous: "<<prev[i]<<endl;
}

実行結果

0 to 1, Cost: 3 Previous: 0
0 to 2, Cost: 5 Previous: 1
0 to 3, Cost: 4 Previous: 1
0 to 4, Cost: 6 Previous: 3
0 to 5, Cost: 7 Previous: 2
0 to 6, Cost: 7 Previous: 4

この出力例では、始点 0 から各頂点への最短コストと、その経路上で直前に通過するノード（Previous）が表示されています。例えば「0 to 6」の場合、コスト 7 で頂点 4 を経由することが分かります。