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

ダイクストラ法とは

ダイクストラ法（Dijkstra's algorithm）は、グラフ上のノード間の最短経路を求めるための代表的なアルゴリズムです。グラフは、例えば道路網などを表現するのに用いられます。このアルゴリズムは、始点（ソース）となる頂点から、グラフ内の他のすべての頂点への最短経路木を構築します。

ダイクストラ法は、始点となる単一のノードから出発し、「始点からの距離が最小となるノードの集合」を段階的に拡張していくことで、最短経路木を求めます。

グラフの構成要素

このアルゴリズムで扱うグラフは、以下の要素で構成されます。

• 頂点（ノード）：アルゴリズム内では v や u といった記号で表されます。
• 重み付き辺：2つのノードを接続する辺で、(u, v) が辺を、w(u, v) がその重みを表します。

アルゴリズムの手順

1. 始点以外のすべての頂点の距離を無限大に設定し、始点の距離を 0 に設定します。
2. 始点を「(距離, 頂点)」の形式で最小優先度キューにプッシュします。キューの比較は頂点の距離に基づいて行われます。
3. 優先度キューから距離が最小の頂点をポップします（最初にポップされるのは始点です）。
4. 「現在の頂点の距離 ＋ 辺の重み ＜ 次の頂点の距離」が成り立つ場合、ポップした頂点に接続された頂点の距離を更新し、新しい距離でその頂点を優先度キューにプッシュします。
5. ポップした頂点がすでに訪問済みの場合は、それを使用せずにスキップします。
6. 優先度キューが空になるまで、同じ処理を繰り返します。

問題設定

グラフと始点の頂点が与えられたとき、始点からグラフ内のすべての頂点への最短経路を求めます。ここで、G[][] はグラフの重み行列、n はグラフの頂点数、u は開始ノードを表します。

入力

G[max][max]={{0,1,0,3,10},
    {1,0,5,0,0},
    {0,5,0,2,1},
    {3,0,2,0,6},
    {10,0,1,6,0}}
n=5
u=0

出力

Distance of node1=1
Path=1<-0
Distance of node2=5
Path=2<-3<-0
Distance of node3=3
Path=3<-0
Distance of node4=6
Path=4<-2<-3<-0

アルゴリズムの考え方

• 隣接行列 adj[][] からコスト行列 C[][] を作成します。C[i][j] は頂点 i から頂点 j へ移動するコストを表し、頂点 i と j の間に辺が存在しない場合は無限大（INFINITY）とします。
• 訪問管理用の配列 visited[] を 0 で初期化します。

for(i=0;i<n;i++)
    visited[i]=0;

• 頂点 0 を始点とする場合、visited[0] を 1 としてマークします。
• 始点（頂点 0）から各頂点（0 ～ n-1）へのコストを格納する距離配列 distance[] を作成します。

for(i=1;i<n;i++)
distance[i]=cost[0][i];

初期状態では、始点自身の距離を 0 とします。つまり distance[0]=0; です。

for(i=1;i<n;i++)
visited[i]=0;

• distance[w] が最小かつ visited[w] が 0 である頂点 w を選択し、visited[w] を 1 としてマークします。
• 残りの頂点について、始点からの最短距離を再計算します。
• 再計算の対象となるのは、visited[] で 1 とマークされていない頂点のみです。つまり、各頂点 v に対して次の更新を行います。

if(visited[v]==0)
    distance[v]=min(distance[v],
    distance[w]+cost[w][v])

C++による実装例

以下は、隣接行列を用いてダイクストラ法を実装したC++のサンプルプログラムです。各ノードへの最短距離と、その経路（どのノードを経由したか）を出力します。

#include<iostream>
#include<stdio.h>
using namespace std;
#define INFINITY 9999
#define max 5
void dijkstra(int G[max][max],int n,int startnode);
int main() {
    int G[max][max]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0,2,0,6},{10,0,1,6,0}};
    int n=5;
    int u=0;
    dijkstra(G,n,u);
    return 0;
}
void dijkstra(int G[max][max],int n,int startnode) {
    int cost[max][max],distance[max],pred[max];
    int visited[max],count,mindistance,nextnode,i,j;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    if(G[i][j]==0)
        cost[i][j]=INFINITY;
    else
        cost[i][j]=G[i][j];
    for(i=0;i<n;i++) {
        distance[i]=cost[startnode][i];
        pred[i]=startnode;
        visited[i]=0;
    }
    distance[startnode]=0;
    visited[startnode]=1;
    count=1;
    while(count<n-1) {
        mindistance=INFINITY;
        for(i=0;i<n;i++)
            if(distance[i]<mindistance&&!visited[i]) {
            mindistance=distance[i];
            nextnode=i;
        }
        visited[nextnode]=1;
        for(i=0;i<n;i++)
            if(!visited[i])
        if(mindistance+cost[nextnode][i]<distance[i]) {
            distance[i]=mindistance+cost[nextnode][i];
            pred[i]=nextnode;
        }
        count++;
    }
    for(i=0;i<n;i++)
    if(i!=startnode) {
        cout<<"
Distance of node"<<i<<"="<<distance[i];
        cout<<"
Path="<<i;
        j=i;
        do {
            j=pred[j];
            cout<<"<-"<<j;
        }while(j!=startnode);
    }
}

計算量について

この実装では、隣接行列を使用して未訪問の頂点から最小距離の頂点を線形探索しているため、計算量は O(V²) となります。頂点数が多いグラフでは、優先度キュー（二分ヒープ）と隣接リストを組み合わせることで、計算量を O((V+E) log V) まで改善できます。また、ダイクストラ法は辺の重みがすべて非負であることが前提となる点にも注意してください。負の重みを含むグラフにはベルマン・フォード法などが適しています。

まとめ

ダイクストラ法は、道路ナビゲーションやネットワークルーティングなど、幅広い分野で活用される基礎的な最短経路アルゴリズムです。本記事で紹介した隣接行列を用いたシンプルな実装を理解することで、アルゴリズムの本質的な動作を把握できます。まずは小規模なグラフで動作を確認し、その後、優先度キューを用いた効率的な実装にも挑戦してみてください。