単一始点最短経路の問題をダイクストラ法と隣接行列を使って解きたいと思います。
問題はALDS1_12_Bを使います。
ダイクストラ法とは
ダイクストラ法は以下のように表される。
前提として、グラフ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]に入っていることになります。
隣接行列を用いたダイクストラ法
上記をふまえて以下のように実装します。
上記の対象の処理には番号を振っています。
#define MAX 100
#define INFTY 1<<22
// 未訪問の頂点を示す
#define WHITE 0
// 訪問済の頂点を示す
#define GRAY 1
// 未探索の頂点d[u]にはINFTYが入っている
#define BLACK 2
// 隣接行列頂点から頂点への辺の重みが入っている
// 例:gMatrix[0][1] 頂点0から1への重み INFTYの場合辺がないことを示す
int gMatrix[MAX][MAX];
void dijkstra(int n){
// 最小の重みを記録する
int minV;
// u[v]に始点sからvまでの最短コストを保存する
int u[MAX];
// 訪問状態を記録
int color[MAX];
// 1.初期化
for(int i = 0;i < n;++i){
u[i] = INFTY;
color[i] = WHITE;
}
// 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];
}
}
if(u == -1)break;
// 選んだ頂点は最短経路決定利用はダイクストラロジック解説にて
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;
}
}
}
}
// 出力
for(int i = 0;i < n;++i){
cout << i << " " << ( weight[i] == INFTY ? -1 : weight[i] ) << endl;
}
}
プリム法と同様wikiに図解されているかなと思ったんですが、
残念ながらのっていませんでいした。
その代わりにアニメーション図がありました、全体の整理でないんでわかりにくい気がしますが。
それでは、ALDS1_12_Bの問題をふまえての全体のプログラムです。
#include <iostream>
using namespace std;
#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;
// weight[v]に始点sからvまでの最短コストを保存する
int weight[MAX];
// 訪問状態を記録
int color[MAX];
// 1.初期化
for(int i = 0;i < n;++i){
weight[i] = INFTY;
color[i] = WHITE;
}
// 始点
weight[0] = 0;
color[0] = GRAY;
while(1){
minV = INFTY;
// 頂点を示す
int u = -1;
// 2.1weight[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){
// 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;
}
}
}
}
// 出力
for(int i = 0;i < n;++i){
cout << i << " " << ( weight[i] == INFTY ? -1 : weight[i] ) << endl;
}
}
int main(){
int n;
cin >> n;
for(int i = 0;i < n;++i){
for(int j = 0;j < n;++j){
gMatrix[i][j] = INFTY;
}
}
int k,c,u,v;
for(int i = 0;i < n;++i){
cin >> u >> k;
for(int j = 0;j < k;++j){
cin >> v >> c;
gMatrix[u][v] = c;
}
}
dijkstra(n);
return 0;
}
最終更新:2020/1/29
0 件のコメント:
コメントを投稿