Dijkstra's Algorithm ダイクストラのアルゴリズム

グラフ G(V, E) における Single Source Shortest Path を求めるためのアルゴリズムの１つが、 Dijkstra によって発見された Dijkstra's Algorithm (ダイクストラのアルゴリズム) です。

Dijkstra's Algorithm は Greedy Algorithm で、以下のように実装します。

	グラフ G(V, E) のノード全体の集合を V、 s をスタート地点 (source)、 S を「 s から S 内の各ノード v への最短経路が必ず S 内にあるような、最短経路の部分的な解の集合」とします（下図を参照して下さい）。
	各計算ステップにおいて、V - S の各ノード v について、S 内のノードのみを経由した s から v への最短経路のコスト(距離)を d[v] とします。また、各ノード間のコスト（距離） (x, y) は、行列 M[x][y] に記録されているものとします。
1.	初期状態で、S は空です。 s に対して     d[s] = 0 s 以外の V に属する全てのノード v に対して     d[v] = ∞ と初期化します。
2.	ノードの集合 V - S の中から、d[u] が最小であるノード u を選択します。
	u を S に追加すると同時に、u に隣接しかつ V - S に属する全てのノード v に対する値を以下のように更新します。
	d[v] = min( d[v], d[u] + M[u][v] )
	この処理を S = V となるまで繰り返します。

以下の図は、u が選ばれた直後、v を更新する様子を示しています。

2. の計算ステップ直後（つまり次に u を選ぶ直前）において、 d[v] には、s から S 内のノードのみを経由した v までの最短コストが記録されています。

すなわち、処理が終了した時点で、V に属する全てのノード d[v] には、s から v までの最短コスト（距離）が記録されています。

コスト（距離）だけでなく、経路も求めたい場合は、Shortest spanning tree における v の親である pi[v] を用意し、pi[s] = -1と初期化し、更新部分を以下のように書き換えます。

もし、d[u] + M[u][v] ＜ d[v] ならば、     d[v] = d[u] + M[u][v]     pi[v] = u;

ダイクストラのアルゴリズムのプログラム例です。

int N;
int M[MAX][MAX];

void dijkstra( int s, int d[] ){
    bool visited[MAX]; // S に属するノードは true
    for ( int i = 0; i < N; i++ ){
        d[i] = INT_MAX;
        visited[i] = false;
    }
    
    d[s] = 0; // 最初に s が u として選ばれる
    
    while( 1 ){
        int u; // 最適なノード u を選ぶ
        int mincost = INT_MAX;
        for ( int i = 0; i < N; i++ ){
            if ( !visited[i] && d[i] < mincost ){
                mincost = d[i]; u = i;
            }
        }
        
        // u が存在しなかったとき、つまり S がこれ以上増えないとき、終了
        if ( mincost == INT_MAX ) break;
        
        visited[u] = true; // u を S に追加
        
        for ( int v = 0; v < N; v++ ){
            // v が S に含まれる場合　または　エッジ(u, v)がない場合は　無視
            if ( visited[v] || M[u][v] == INT_MAX ) continue;
            
            d[v] = min( d[v], d[u] + M[u][v] );
        }
    }
}

経路を生成するために pi を加えたプログラムです。

001 int N;
002 int M[MAX][MAX];
003 
004 void dijkstra( int source, int d[], int pi[] ){
005     bool visited[MAX]; // S に属するノードは true
006     for ( int i = 0; i < N; i++ ){
007         d[i] = INT_MAX;
008         visited[i] = false;
009     }
010     
011     d[source] = 0; // 最初に s が u として選ばれる
012     pi[source] = -1;
013     
014     while( 1 ){
015         int u; // 最適なノード u を選ぶ
016         int mincost = INT_MAX;
017         for ( int i = 0; i < N; i++ ){
018             if ( !visited[i] && d[i] < mincost ){
019                 mincost = d[i]; u = i;
020             }
021         }
022         
023         // u が存在しなかったとき、つまり S がこれ以上増えないとき、終了
024         if ( mincost == INT_MAX ) break;
025         
026         visited[u] = true; // u を S に追加
027         
028         for ( int v = 0; v < N; v++ ){
029             // v が S に含まれる場合　または　エッジ(u, v)がない場合は　無視
030             if ( visited[v] || M[u][v] == INT_MAX ) continue;
031             if ( d[u] + M[u][v] < d[v] ){
032                 d[v] = d[u] + M[u][v];
033                 pi[v] = u;
034             }
035         }
036     }
037 }