fc2ブログ



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 を選択します。
uS に追加すると同時に、u に隣接しかつ V - S に属する全てのノード v に対する値を以下のように更新します。
    d[v] = min( d[v], d[u] + M[u][v] )
この処理を S = V となるまで繰り返します。

dijkstraStep.gif

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

relax.gif

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) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ