俺でも理解できるようにダイクストラ法のアルゴリズムを解説します。
目次
- 理解に必要な前提知識
- ダイクストラ法について
- ダイクストラ法の手順
- ダイクストラ法の図解
- なぜ、最小コストの頂点が最短経路になるのか
- ダイクストラ法のサンプルプログラム
- 練習例題一覧
- まとめ
- 参考ソース
理解に必要な前提知識
グラフの知識
ダイクストラ法について
ダイクストラ法は単一最短経路を求める場合に使われるアルゴリズムです。
単一最短経路とは、グラフ内で一つ始点を定めてそこから派生する頂点への最短経路を求めること>を言います。
ダイクストラ法の手順
前提として、グラフG = (V(頂点),E(辺))の頂点全体の集合をV、始点をs、
最短経路木に含まれる頂点の集合をSとします。
各計算のステップで、最短経路木の辺と頂点を選びSへ追加していきます。
また、各頂点iについて、S内の頂点のみを経由したsからiへの最短経路のコストをd[i]とします。
ここから、手順に入ります。
1.初期化処理
最短経路木に含まれる頂点の集合をSを以下のように初期化します。
始点sに対して最短経路のコストを示すd[s] = 0を代入し、
始点s以外の頂点の全体集合Vに属する全ての頂点iに対してd[i] = 最大値
を代入します。
2.以下の処理をS = Vになるまで(始点sから各々の頂点の最短経路が求まるまで)続けます。
2.1
V - Sの中から、d[u]が最小である頂点uを選択(最短経路と決定している頂点を除く)します。
2.2
頂点uをSに追加すると同時に、uに隣接しかつV - Sに属する全ての頂点vに対する
値を以下のように更新します。
if d[u] + w(u,v)(実際にかかる移動コスト) < d[v] d[v] = d[u] + w(u,v)
2.の各計算ステップ直後に,
u[v]には、sからSの頂点のみを経由したvまでの最短コストが記録されていることになります。
つまり1,2の処理が全て終了すると、u[v]に,sからvまでの最短コストが記録されることになります。
ダイクストラ法の図解
プロセスがわかりやすいように、ダイクストラ法を図解してみます。
下図のようなグラフがあり、始点をAをとします。 Aから各々の頂点への最短経路をダイクストラで求めてみます。
まず、始点Aを0で初期化し、各々への頂点に探索が完了していないことを示すために最大値を代入(変数d[]が対象となる)します。
出典:MIT open course ware
ここから、2.のプロセスに入ります。
最短経路木を示す頂点の集合をSとして、Sを以下のように表します。
S = {} {A B C D E }(Sから各頂点の最短経路の重さを示します。)
step1
まず、始点(s)である頂点AをSに追加します。
S = {A} {0 ∞ ∞ ∞ ∞ }
続いて、頂点Aに辺があり、最短経路未決定の頂点の最短経路を更新します。
最短経路か判定する式は、
if d[u] + w(u,v) < d[v] d[v] = d[u] + w(u,v)
なので、Aに隣接する頂点B,Cは頂点uが始点で重みが0なので、 辺への重みのみが加算され、以下のようになります。
S = {A} {0 10 3 ∞ ∞ }
step2
また、2.1のプロセスに戻ります。
2.1:V - Sの中から、d[u]が最小である頂点uを選択します。
つまり、最短距離未決定の最小頂点C(重み3)を選ぶことになりますが、
なぜ、最小コストの頂点を選んだ時点で、その地点が最短経路になるのかを、
図で考えてみます。
なぜ、最小コストの頂点が最短経路になるのか
下図のように始点から辺が3つ伸びているグラフがあるとします。
グラフより、各々の3つの頂点からその3つの頂点への辺があるとしても、
sから各々の頂点への3つの辺の中に必ず最短となる経路があることがわかります。
これは、辺が2つでも4つでも同じことです。
step2に戻ります。
Sに最短経路である頂点Cを追加します。
S = {A C} {0 10 3 ∞ ∞ }
続いて、Cにつながる頂点への最短経路更新プロセスに入り、
図を参考に以下のように更新します。
S = {A C} {0 7 3 11 5 }
step3
プロセス1に戻って、探索を開始する頂点を決定します。
最短点であるE(5)が選ばれるので、EをSに追加します。
S = {A C E} {0 7 3 11 5 }
プロセス2に移り、頂点Eにつながる頂点の最短点の更新を行います。
更新する頂点はないので、結果は前と変わりません。
S = {A C E} {0 7 3 11 5 }
step4
プロセス1に戻って、探索を開始する頂点を決定します。
最短点であるB(7)が選ばれるので、BをSに追加します。
S = {A C E B} {0 7 3 11 5 }
プロセス2に移り、頂点Bにつながる頂点の最短点の更新を行います。 頂点Dへの最短経路が9に変わります。
S = {A C E B} {0 7 3 9 5 }
step5
プロセス1に戻って、探索を開始する頂点を決定します。
ここで、全ての最短経路がもとまったので、処理を終了します。
始点sから頂点uへの最短経路はd[u]に入っていることになります。
ダイクストラ法のサンプルプログラム
隣接行列を使った、ダイクストラの実装方法について解説します。
隣接行列とは
隣接行列には、以下のように一次元に頂点、2次元に辺への重みを入れます。
頂点から頂点への辺が繋がっていない場合は最大値を定義しその最大値を代入します。
例として、頂点が3つ(A,C,B)とし、
AからB(重み3)への辺
BからC(重み4)への辺
CからA(重み5)への辺
をもつグラフを隣接行列にすると以下のようになります。
matrix[][] =
{∞,3,∞},
{∞,∞,4},
{5,∞,∞};
隣接行列への説明が終わったところで、実装に入ります。
まず、必要変数を定義します。
// 最大頂点数
#define MAX 100
// 未訪問または、辺がないことを示す最大数値
#define INFTY 1<<22
// 未訪問の頂点を示す
#define WHITE 0
// 訪問済の頂点を示す
#define GRAY 1
// 最短経路決定済の頂点を示す
#define BLACK 2
// 隣接行列頂点から頂点への辺の重みが入っている
// 例:gMatrix[0][1] 頂点0から1への重み INFTYの場合辺がないことを示す
int gMatrix[MAX][MAX];
// 最小の重みを記録する
int minV;
// u[v]に始点sからvまでの最短コストを保存する
int u[MAX];
// 始点から書く頂点への訪問状態を記録
int color[MAX];
では、ダイクストラを求める関数の解説をします。
まずは、初期化プロセスです。
void dijkstra(int n){
// 1.初期化
for(int i = 0;i < n;++i){
u[i] = INFTY;
color[i] = WHITE;
}
// 0を始点とする(頂点A,B,C...としCから始めたい場合は、u[2]=0とする)
u[0] = 0;
color[0] = GRAY;
初期はプロセスは、そのままですね。
続いて、最短経路を決定するロジックの部分です。
while(1){
minV = INFTY;
// uは探索対象となる頂点を示す
int u = -1;
// 2.1 d[u]が最小である頂点を決定する
for(int i = 0;i < n;++i){
// 最短経路決定ずみの頂点は含めない
if(minV > weight[i] && color[i] != BLACK){
u = i;
minV = weight[i];
}
}
// u == -1の場合始点から各々への頂点への最短経路が求まっていることになる
if(u == -1)break;
// d[u]が最小となる頂点が最短経路になることは、解説済
color[u] = BLACK;
// 頂点からつながる各々の頂点への最短経路を更新する
for(int v = 0;v < n;++v){
// 辺が存在し、最短経路決定済頂点以外の経路が対象になる。
if(color[v] != BLACK && gMatrix[u][v] != INFTY){
// 2.2最短コストを更新する
// この処理の終了後weight[v]sからS内の頂点のみを経由したvまでの最短コストが記録される
if(weight[v] > weight[u] + gMatrix[u][v]){
weight[v] = weight[u] + gMatrix[u][v];
color[v] = GRAY;
}
}
}
}
全体のコードは以下になります。
#define MAX 100
#define INFTY 1<<22
#define WHITE 0
#define GRAY 1
#define BLACK 2
int gMatrix[MAX][MAX];
void dijkstra(int n){
int minV;
int u[MAX];
int color[MAX];
for(int i = 0;i < n;++i){
u[i] = INFTY;
color[i] = WHITE;
}
u[0] = 0;
color[0] = GRAY;
while(1){
minV = INFTY;
int u = -
for(int i = 0;i < n;++i){
if(minV > weight[i] && color[i] != BLACK){
u = i;
minV = weight[i];
}
}
if(u == -1)break;
color[u] = BLACK;
for(int v = 0;v < n;++v){
if(color[v] != BLACK && gMatrix[u][v] != INFTY){
if(weight[v] > weight[u] + gMatrix[u][v]){
weight[v] = weight[u] + gMatrix[u][v];
color[v] = GRAY;
}
}
}
}
// 始点からつながる各々の頂点への最短経路を出力
for(int i = 0;i < n;++i){
cout << i << " " << ( weight[i] == INFTY ? -1 : weight[i] ) << endl;
}
}
練習例題一覧
ダイクストラ法で解けるonline judgeの例題をあげます。
例題1
ALDS1_12_B
頂点の数が少ないので、隣接行列を使って解くことができます。
問題の解法ををこちらにまとめました。
例題2
ALDS1_12_C
問題は同じですが、頂点数が多いため解法を工夫する必要があります。
優先度付きqueを使った解法をこちらでまとめています。
例題3
GRL_1_A
例題2と内容は同じですが、与えられる入力が異なります。
まとめ
最短経路の頂点に隣接する頂点のうち、重みが最短のものが最短経路となり、
このロジックを繰り返すことで、最短経路が求まるというのがポイントです。
わかりにくかったり、誤りがあった場合は、コメントください。
参考ソース
理解するのに、プロコンのためのアルゴリズムとデータ構造と
MITのopen course wareに単一最短始点経路とダイクストラ法の解説動画ををみました。
