DAG（有向非巡回グラフ）におけるSSSP（単一始点最短経路）を求めるC++プログラム

本記事では、ダイクストラ法を用いて有向非巡回グラフ（DAG：Directed Acyclic Graph）における単一始点最短経路（SSSP：Single Source Shortest Path）を求めるC++プログラムを紹介します。このプログラムは、グラフの始点となる最初のノードから他のすべてのノードへの最短経路長を計算し、各頂点に対してそのコストを出力します。

アルゴリズム

まず、グラフの重みを隣接行列として入力し、その後ダイクストラ法の手法に従って最短経路を求めていきます。処理で使われる主な変数は次のとおりです。

• a[i]：ノード i が確定済みかどうかを示すフラグ（1＝確定済み）
• d[i]：始点からノード i までの現時点での最短距離
• s[i].from：ノード i に至る直前のノード（経路の履歴情報）
• b[i][j]：ノード i から j への辺の重みを格納した隣接行列

全体の流れは以下の擬似コードのとおりです。

開始
　　グラフの要素を入力として受け取る
　　関数 shortestpath()：
　　　　変数を初期化する
　　　　a[i] = 1
　　　　d[i] = 0
　　　　s[i].from = 0
　　　　i = 0 ～ 3 についてループ
　　　　　　b[0][i] == 0 の場合は continue
　　　　　　それ以外の場合は
　　　　　　　　d[i] = b[0][i]
　　　　　　　　s[i].from = 0
　　　　　　終了
　　　　終了
　　　　while (c < 4) の間ループ
　　　　　　min = INFINITY に初期化
　　　　　　i = 0 ～ 3 についてループ
　　　　　　　　min <= d[i] または d[i] == 0 または a[i] == 1 の場合は continue
　　　　　　　　min > d[i] の場合は min = d[i]
　　　　　　終了
　　　　　　k = 0 ～ 3 についてループ
　　　　　　　　min == d[k] の場合
　　　　　　　　　　t = k
　　　　　　　　　　break
　　　　　　　　それ以外の場合は continue
　　　　　　　　終了
　　　　　　a[t] = 1 に設定
　　　　　　j = 0 ～ 3 についてループ
　　　　　　　　a[j] == 1 または b[t][j] == 0 の場合は continue
　　　　　　　　それ以外の場合
　　　　　　　　　　d[j] > (d[t] + b[t][j]) であれば
　　　　　　　　　　　　d[j] = d[t] + b[t][j]
　　　　　　　　　　　　s[i].from = t
　　　　　　c をインクリメント
　　　　終了
　　　　i = 0 ～ 3 についてループ
　　　　　　ノード1からノード2への最小コストを出力
　　　　終了
終了

このアルゴリズムは「未確定のノードの中から最も近いノードを選び、そこを経由した方が距離が短くなるノードの距離を更新する」というダイクストラ法の基本手順を繰り返すことで、全ノードへの最短距離を確定させていきます。計算量は O(V²) であり、辺の重みがすべて非負であることが前提となります。

C++による実装例

#include <iostream>
using namespace std;
#define INFINITY 9999
struct node {
    int from;
} s[4];
int c = 0;
void djikstras(int *a, int b[][4], int *d) {
    int i = 0, j, min, t;
    a[i] = 1;
    d[i] = 0;
    s[i].from = 0;
    for (i = 0; i < 4;i++) {
        if (b[0][i] == 0) {
            continue;
        } else {
            d[i] = b[0][i];
            s[i].from = 0;
        }
    }
    while (c < 4) {
        min = INFINITY;
        for (i = 0; i < 4; i++) {
            if (min <= d[i] || d[i] == 0 || a[i] == 1) {
                continue;
            } else if (min > d[i]) {
                min = d[i];
            }
        }
        for (int k = 0; k < 4; k++) {
            if (min == d[k]) {
                t = k;
                break;
            } else {
                continue;
            }
        }
        a[t] = 1;
        for (j = 0; j < 4; j++) {
            if (a[j] == 1 || b[t][j] == 0) {
                continue;
            } else if (a[j] != 1) {
                if (d[j] > (d[t] + b[t][j])) {
                    d[j] = d[t] + b[t][j];
                    s[i].from = t;
                }
            }
        }
        c++;
    }
    for (int i = 0; i < 4; i++) {
        cout<<"from node "<<s[i].from<<" cost is:"<<d[i]<<endl;
    }
}
int main() {
    int a[4];
    int d[4];
    for(int k = 0; k < 4; k++) {
        d[k] = INFINITY;
    }
    for (int i = 0; i < 4; i++) {
        a[i] = 0;
    }
    int b[4][4];
    for (int i = 0;i < 4;i++) {
        cout<<"enter values for "<<(i+1)<<" row"<<endl;
        for(int j = 0;j < 4;j++) {
            cin>>b[i][j];
        }
    }
    djikstras(a,b,d);
}

main関数では、まず距離配列 d を無限大（ここでは9999）で初期化し、確定フラグ配列 a を0で初期化しています。その後、4×4の隣接行列を標準入力から受け取り、djikstras関数を呼び出して最短経路を計算します。

出力結果

enter values for 1 row
0
1
3
2
enter values for 2 row
2
1
3
0
enter values for 3 row
2
3
0
1
enter values for 4 row
1
3
2
0
from node 0 cost is:0
from node 0 cost is:1
from node 0 cost is:3
from node 0 cost is:2

この実行例では、4×4の隣接行列を入力として与えています。プログラムはノード0を始点として各ノードへの最短コストを計算し、「from node ○ cost is:△」という形式で結果を出力します。実行結果より、ノード0自身のコストは0、ノード1へは1、ノード2へは3、ノード3へは2であることが確認できます。