Dijkstra's Algorithm ダイクストラのアルゴリズム
2006.05.15 00:38 グラフ 最短経路
グラフ G(V, E) における Single Source Shortest Path を求めるためのアルゴリズムの1つが、 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 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |