単一始点最短経路問題（非負の重み）――ダイクストラ法の解説とC++実装

非負の重みを持つグラフにおける単一始点最短経路問題を解くアルゴリズムは、「ダイクストラ法（Dijkstra's algorithm）」として広く知られています。隣接行列で表現されたグラフ G(V,E) と始点（ソース頂点）が与えられたとき、ダイクストラ法を用いることで、始点からグラフ内の他のすべての頂点への最小コストの経路（最短経路）を求めることができます。

下図のように、開始ノードから他の各ノードまでの最小距離を求めるのが目的です。この問題では、グラフは隣接行列で表現します（この用途ではコスト行列と隣接行列は同じものとして扱えます）。

入力例：隣接行列

0 3 6 ∞ ∞ ∞ ∞
3 0 2 1 ∞ ∞ ∞
6 2 0 1 4 2 ∞
∞ 1 1 0 2 ∞ 4
∞ ∞ 4 2 0 2 1
∞ ∞ 2 ∞ 2 0 1
∞ ∞ ∞ 4 1 1 0

出力例

0 to 1, Using: 0, Cost: 3

0 to 2, Using: 1, Cost: 5

0 to 3, Using: 1, Cost: 4

0 to 4, Using: 3, Cost: 6

0 to 5, Using: 2, Cost: 7

0 to 6, Using: 4, Cost: 7

出力の「Using」は、その頂点へ至る直前に通過する頂点（直前ノード）を、「Cost」は始点からその頂点までの総コストを表します。たとえば「0 to 5, Using: 2, Cost: 7」は、頂点0から頂点5へは頂点2を経由し、合計コスト7で到達できることを意味します。

アルゴリズム

dijkstraShortestPath(n, dist, next, start)

入力 ― ノードの総数 n、各頂点の距離を格納するリスト dist、次にどのノードへ進むかを記録するリスト next、そして始点（スタート頂点）start。

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

Begin
    選択済みノードの状態を保持するためのステータスリストを作成する
    V 内のすべての頂点 u について
        status[u] := 未考慮
        dist[u] := コスト行列を用いて計算した始点からの距離
        next[u] := start
    繰り返し終了
    status[start] := 考慮済み、dist[start] := 0、next[start] := φ
    while 距離が最小となる未考慮の頂点 u を選択できる間
        status[u] := 考慮済み
        V 内のすべての頂点 v について
            if status[v] = 未考慮 then
                if dist[v] > dist[u] + cost[u,v] then
                    dist[v] := dist[u] + cost[u,v]
                    next[v] := u
        繰り返し終了
    繰り返し終了
End

このアルゴリズムの計算量は、隣接行列を用いた場合 O(V²) となります。優先度付きキュー（ヒープ）を併用すれば、O((V+E) log V) まで改善できる点も覚えておくとよいでしょう。

C++による実装例

#include<iostream>
#define V 7
#define INF 999
using namespace std;
// グラフのコスト行列
int costMat[V][V] = {
    {0, 3, 6, INF, INF, INF, INF},
    {3, 0, 2, 1, INF, INF, INF},
    {6, 2, 0, 1, 4, 2, INF},
    {INF, 1, 1, 0, 2, INF, 4},
    {INF, INF, 4, 2, 0, 2, 1},
    {INF, INF, 2, INF, 2, 0, 1},
    {INF, INF, INF, 4, 1, 1, 0}
};
int minimum(int *status, int *dis, int n){
    int i, min, index;
    min = INF;
    for(i = 0; i<n; i++)
        if(dis[i] < min && status[i] == 1){
            min = dis[i];
            index = i;
        }
    if(status[index] == 1)
        return index;// 最小距離の未考慮頂点を返す
    else
        return -1;// すべての頂点が考慮済みの場合
}
void dijkstra(int n, int *dist,int *next, int s){
    int status[V];
    int u, v;
    // 初期化
    for(u = 0; u<n; u++){
        status[u] = 1;// 未考慮の頂点
        dist[u] = costMat[u][s];// 始点からの距離
        next[u] = s;
    }
    // 始点自体の設定
    status[s] = 2; dist[s] = 0; next[s] = -1;// -1 は始点を意味する
    while((u = minimum(status, dist, n)) > -1){
        status[u] = 2;// ここで考慮済みにする
        for(v = 0; v<n; v++)
            if(status[v] == 1)
                if(dist[v] > dist[u] + costMat[u][v]){
                    dist[v] = dist[u] + costMat[u][v];// 距離を更新
                    next[v] = u;
                }
    }
}
main(){
    int dis[V], next[V], i, start = 0;
    dijkstra(V, dis, next, start);
    for(i = 0; i<V; i++)
        if(i != start)
            cout << start << " to " << i <<", Using: " << next[i] << ", Cost: " << dis[i] << endl;
}

実行結果

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

このように、ダイクストラ法を使えば、非負の重みを持つグラフにおいて、始点からすべての頂点への最短経路とそのコストを効率的に求めることができます。辺の重みに負の値が含まれる場合はベルマン・フォード法など別の手法が必要になるため、適用条件には注意しましょう。