セット(集合)を用いたダイクストラ法のC++実装|アルゴリズム解説とサンプルコード

これは、セット(集合)を使用してダイクストラ法(Dijkstra's Algorithm)を実装するC++プログラムです。この手法では2つの集合を扱います。与えられた始点ノードを根として最短経路木を構築し、一方の集合には最短経路木に既に含まれた頂点を、もう一方の集合にはまだ含まれていない頂点を格納します。そして各ステップごとに、未確定の集合の中から始点からの距離が最小となる頂点を見つけ出します。

アルゴリズムの手順

開始
    最短距離を求める関数 dijkstra():
    1) 最短経路木に含まれる頂点を記録するための集合 Set を作成する。
       初期状態では、この集合は空である。
    2) 入力グラフ内のすべての頂点に距離値を割り当てる。
       すべての距離値は無限大(INFINITE)で初期化し、
       始点頂点のみ距離値を 0 として、最初に選ばれるようにする。
    3) 集合がすべての頂点を含むまで以下を繰り返す:
       a) 集合に含まれておらず、かつ距離値が最小である頂点 u を選ぶ。
       b) 頂点 u を集合に追加する。
       c) u のすべての隣接頂点について距離値を更新する。
          更新の際は全隣接頂点を走査し、隣接頂点 v それぞれに対して、
          「u の距離値(始点から)+ 辺 u-v の重み」が v の現在の
          距離値より小さければ、v の距離値をその値で更新する。
終了

サンプルコード

#include <iostream>
#include <climits>
#include <set>
using namespace std;
#define N 5
 
// 未確定頂点の中から最小距離の頂点を探す
int minDist(int dist[], bool Set[])
{
    int min = INT_MAX, min_index;
    for (int v = 0; v < N; v++)
        if (Set[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}
 
// 結果を出力する
int printSol(int dist[], int n)
{
    cout << "始点からの各頂点への最短距離\n";
    for (int i = 0; i < N; i++)
        cout << i << "\t\t" << dist[i] << "\n";
}
 
void dijkstra(int g[N][N], int src)
{
    int dist[N];
    bool Set[N];
    for (int i = 0; i < N; i++)
        dist[i] = INT_MAX, Set[i] = false;
    dist[src] = 0;
    for (int c = 0; c < N - 1; c++) {
        int u = minDist(dist, Set);
        Set[u] = true;
        for (int v = 0; v < N; v++)
            if (!Set[v] && g[u][v]
                && dist[u] != INT_MAX
                && dist[u] + g[u][v] < dist[v])
                dist[v] = dist[u] + g[u][v];
    }
    printSol(dist, N);
}
 
int main()
{
    int g[N][N] = { { 0, 4, 0, 0, 0 },
        { 4, 0, 7, 0, 0 },
        { 0, 8, 0, 9, 0 },
        { 0, 0, 7, 0, 6 },
        { 0, 2, 0, 9, 0 } };
    dijkstra(g, 0);
    return 0;
}

実行結果

始点からの各頂点への最短距離
0        0
1        4
2        11
3        20
4        26

コードの解説

minDist 関数

まだ最短経路木に含まれていない頂点(Set[v] == false)の中から、距離値が最小の頂点のインデックスを線形探索によって返します。この関数が、各ステップで「次に確定すべき頂点」を選択する役割を担っています。

dijkstra 関数

全頂点の距離値を無限大(INT_MAX)で初期化し、始点のみ 0 に設定した後、N-1 回のループで処理を繰り返します。各ループでは minDist で最小距離の未確定頂点 u を選んで確定し(Set[u] = true)、u に隣接する未確定頂点 v に対して距離の緩和(リラクゼーション)を行います。辺が存在し(g[u][v] が非ゼロ)、u の距離が確定済みで、dist[u] + g[u][v] が dist[v] より小さい場合にのみ更新されます。

main 関数

5頂点のグラフを隣接行列として定義しています(要素が 0 の場合は辺が存在しないことを意味します)。ここでは簡単のため、記事冒頭で説明した「集合」をブール型配列 Set で表現しており、true なら最短経路木に含まれていることを示します。

計算量について

この実装では最小距離の頂点選択に線形探索を用いているため、時間計算量は O(V²) となります。頂点数が多く辺が密なグラフに適した方式です。なお、std::set や優先度付きキュー(binary heap)を用いて未確定頂点を管理すれば、計算量を O((V+E) log V) まで改善できるため、疎なグラフではそちらが有利になります。