ダイクストラ法による最短経路探索|隣接行列を用いたC++実装

この問題は前回のものと基本的に同じで、始点ノードから他のすべてのノードへの最小距離を求めることが目的です。最大の違いは、グラフを隣接行列(この用途ではコスト行列もほぼ同じ役割を果たします)で表現している点です。

隣接行列を用いた場合の時間計算量は O(V²) です。ここで V はグラフ G(V, E) のノード数を表します。

入力と出力

入力:隣接行列



出力:

0 から 1 へ、経由: 0、コスト: 3

0 から 2 へ、経由: 1、コスト: 5

0 から 3 へ、経由: 1、コスト: 4

0 から 4 へ、経由: 3、コスト: 6

0 から 5 へ、経由: 2、コスト: 7

0 から 6 へ、経由: 4、コスト: 7

アルゴリズム

dijkstraShortestPath(n, dist, next, start)

入力 − ノードの総数 n、各頂点の距離を格納するリスト、次に通るノードを記録する next リスト、そして始点(シード)となる頂点。

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

Begin
    選択したノードの現在の状態を保持するステータスリストを作成する
    V 内のすべての頂点 u について
        status[u] := 未考慮
        dist[u] := コスト行列から求めた始点からの距離
        next[u] := start
    done

    status[start] := 考慮済み、dist[start] := 0、next[start] := φ
    while 未考慮の頂点の中から距離が最小の頂点 u を取り出せる間 do
        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 if
            end if
        done
    done
End

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;
    }

    // 始点頂点の設定(-1 は始点であることを示す)
    status[s] = 2; dist[s] = 0; next[s] = -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;
                }
    }
}

int 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 << " から " << i << " へ、経由: " << next[i]
                 << "、コスト: " << dis[i] << endl;
}

実行結果

0 から 1 へ、経由: 0、コスト: 3

0 から 2 へ、経由: 1、コスト: 5

0 から 3 へ、経由: 1、コスト: 4

0 から 4 へ、経由: 3、コスト: 6

0 から 5 へ、経由: 2、コスト: 7

0 から 6 へ、経由: 4、コスト: 7

ダイクストラ法では、「まだ確定していない頂点の中から最も近い頂点を選び、その頂点を経由することで他の頂点への距離を短縮できるか」を繰り返し確認します。これにより、始点からすべての頂点への最短経路を効率的に求めることができます。