C/C++で実装するダイクストラ法｜最短経路アルゴリズムの仕組みとサンプルコード

ダイクストラ法とは

始点（ソース頂点）を持つ重み付きグラフが与えられたとき、その始点からグラフ内の他のすべての頂点への最短経路を求める必要があります。

ダイクストラ法（Dijkstra's algorithm）は、貪欲法（グリーディアルゴリズム）に基づく代表的な最短経路探索アルゴリズムです。「現時点で最も近い未訪問の頂点を確定していく」という考え方により、始点から各頂点までの最小コストを効率的に求めることができます。なお、ダイクストラ法が正しく動作するのは辺の重みがすべて非負の場合である点に注意してください。

アルゴリズムの手順

Step 1 : 最短経路木に含まれる頂点を格納するための集合 shortPath を作成する。
Step 2 : すべての頂点の距離値を無限大（INFINITE）で初期化し、始点の距離値のみ 0 に設定する。これにより、始点が最初に選択される。
Step 3 : グラフのすべての頂点が shortPath に含まれるまで、以下の処理を繰り返す。
    Step 3.1 : 未訪問かつ距離が最小となる頂点を新たに選ぶ。
    Step 3.2 : 選んだ頂点を shortPath に追加する。
    Step 3.3 : その頂点のすべての隣接頂点 v について距離を更新する。「現在の頂点 u までの距離」と「辺 (u, v) の重み」の合計が、v の現在の距離より小さければ値を更新する。

このアルゴリズムに基づいて、実際にプログラムを作成してみましょう。

C言語による実装例

以下のサンプルコードでは、9つの頂点を持つグラフを隣接行列として表現し、頂点0を始点として各頂点への最短距離を計算しています。辺が存在しない箇所は 0 で表しています。

#include <limits.h>
#include <stdio.h>
#define V 9

int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
    if (sptSet[v] == false && dist[v] <= min)
        min = dist[v], min_index = v;
    return min_index;
}

int printSolution(int dist[], int n) {
    printf("Vertex Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t %d\n", i, dist[i]);
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
    dist[src] = 0;
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v];
    }
    printSolution(dist, V);
}

int main() {
    int graph[V][V] = { { 0, 6, 0, 0, 0, 0, 0, 8, 0 },
        { 6, 0, 8, 0, 0, 0, 0, 13, 0 },
        { 0, 8, 0, 7, 0, 6, 0, 0, 2 },
        { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
        { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
        { 0, 0, 6, 14, 10, 0, 2, 0, 0 },
        { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
        { 8, 13, 0, 0, 0, 0, 1, 0, 7 },
        { 0, 0, 2, 0, 0, 0, 6, 7, 0 }
    };
    dijkstra(graph, 0);
    return 0;
}

実行結果

Vertex Distance from Source
0  0
1  6
2  14
3  21
4  21
5  11
6  9
7  8
8  15

出力の各行は「頂点番号」と「始点（頂点0）からの最短距離」のペアを表しています。例えば、頂点7への最短距離は 8、頂点3および頂点4への最短距離は 21 であることが読み取れます。

計算量について

この実装では、未訪問の頂点から最小距離のものを線形探索で選んでいるため、時間計算量は O(V²) となります。頂点数 V に対して辺数 E が少ないスパースなグラフでは、優先度付きキュー（二分ヒープ）を用いることで O((V+E) log V) まで高速化できるため、大規模なグラフを扱う場合にはそちらの実装も検討するとよいでしょう。