「ダイクストラ法」(2010/06/23 (水) 11:20:26) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
**ダイクストラ法
&bold(){ダイクストラ法(Dijkstra's algorithm)}とは,グラフ上の２点間の最短経路を
効率よく求めるアルゴリズムです。ただしエッジに負のコストがあると使えないアルゴリズムとなっています。
このページは[[グラフとは]]のページを見たことを前提に説明していますので、目を通してください。
このページではダイクストラ法をいかにしてC++でコーディングするかに注目するため、
ダイクストラ法のアルゴリズムの詳細は説明しません。下記のリンク先のページを見てください。
[[wikipedia>>http://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95]]
[[ACM/ICPC国内予選突破の手引き>>http://www.deqnotes.net/acmicpc/dijkstra/]]
[[グラフとは]]のページでグラフの情報を構造体として扱いましたが、
ダイクストラ法のためにメンバ変数を追加します。
struct Node{
vector<int> to; //どのノードとつながっているか
vector<int> cost; //エッジのコスト
//ここから下はダイクストラ法のために必要な情報
bool done; //確定ノードかどうか
int minCost; //スタートノードからのコスト
int from; //どのノードから来たか
};
またエッジを追加する関数は
//エッジを追加する関数
void addEdge(int v, int u, int weight, struct Node *node){
//ノードuはノードvとつながっている情報を入れる
node[ u ].to.push_back( v );
//ノードuとノードvのエッジの重みを入れる
node[ u ].cost.push_back( weight );
//有向グラフならここから下の処理が不要
//ノードvはノードuとつながっている情報を入れる
node[ v ].to.push_back( u );
//ノードvとノードuのエッジの重みを入れる
node[ v ].cost.push_back( weight );
}
この関数は[[グラフとは]]のページと同じものです。
この関数を呼び出すことで必要なエッジを追加することができます。
***ダイクストラ法のソースコード
グラフの情報がすべて構造体nodeに入っている状態で
関数dijkstra()にノード数n、スタートノードの番号start、ゴールノードの番号end、構造体node,
を渡すと最短経路を求めてくれます。
//ダイクストラ法
void dijkstra(int n, int start, int end, struct Node *node){
//変数の初期化
for(int i=0 ; i<n ; i++){
node[i].done = false;
node[i].minCost = -1;
}
node[start].minCost = 0; //スタートノードまでのコストは0
while(1){
int doneNode = -1; //最新の確定したノード番号(-1はNULLのかわり)
for(int i=0 ; i<n ; i++){
if( node[i].done==true ){//ノードiが確定しているときcontinue
continue;
}
if( node[i].minCost < 0 ){//ノードiまでの現時点での最小コストが不明のとき
continue;
}
//確定したノード番号が-1かノードiの現時点の最小コストが小さいとき
//確定ノード番号を更新する
if( doneNode<0 || node[i].minCost < node[doneNode].minCost){
doneNode = i;
}
}
if(doneNode==-1) break; //すべてのノードが確定したら終了
node[doneNode].done = true; //ノードを確定させる
for(int i=0 ; i<node[doneNode].to.size() ; i++){
int to = node[doneNode].to[i];
int cost = node[doneNode].minCost + node[doneNode].cost[i];
//ノードtoはまだ訪れていないノード
//またはノードtoへより小さいコストの経路だったら
//ノードtoの最小コストを更新
if( node[to].minCost < 0 || cost < node[to].minCost ){
node[to].minCost = cost;
node[to].from = doneNode;
}
}
}
}
&bold(){最短経路を出力したい場合には}
vector<int> path;//最短経路の情報を保持するvector
//最短経路をゴールから順にスタートまでたどる
for(int i = end ; i != start ; i = node[i].from ){
path.push_back(i);
}
path.push_back(start);
//最短経路の出力
cout << "最短経路は" << endl;
for(int i = path.size()-1 ; i >= 0 ; i--){
cout << path[i] << " ";
}
cout << endl;
上の処理を関数dijkstra()を呼び出した後にmain関数に書くといいです。
最後に余分な空白文字がでるので気をつけてください。
&bold(){最短距離を出力したい場合には}
cout << node[end].minCost << endl;
と関数dijkstra()を呼び出した後にmain関数に書いてください。
***まとめのソースコード
#region(open,ダイクストラ法のソースプログラム)
/*
* dijkstra.cpp
* by otaks , 2010-06-20
*/
#include <iostream>
#include <vector>
using namespace std;
//ノードの数
#define NODE_NUM 10
struct Node{
vector<int> to; //どのノードとつながっているか
vector<int> cost; //エッジのコスト
//ここから下はダイクストラ法のために必要な情報
bool done; //確定ノードかどうか
int minCost; //スタートノードからのコスト
int from; //どのノードから来たか
};
//エッジを追加する関数
void addEdge(int v, int u, int weight, struct Node *node){
//ノードuはノードvとつながっている情報を入れる
node[ u ].to.push_back( v );
//ノードuとノードvのエッジの重みを入れる
node[ u ].cost.push_back( weight );
//有向グラフならここから下の処理が不要
//ノードvはノードuとつながっている情報を入れる
node[ v ].to.push_back( u );
//ノードvとノードuのエッジの重みを入れる
node[ v ].cost.push_back( weight );
}
// ダイクストラ法
void dijkstra(int n, int start, int end, struct Node *node){
//変数の初期化
for(int i=0 ; i<n ; i++){
node[i].done = false;
node[i].minCost = -1;
}
node[start].minCost = 0; //スタートノードまでのコストは0
while(1){
int doneNode = -1; //最新の確定したノード番号(-1はNULLのかわり)
for(int i=0 ; i<n ; i++){
if( node[i].done==true ){//ノードiが確定しているときcontinue
continue;
}
if( node[i].minCost < 0 ){//ノードiまでの現時点での最小コストが不明のとき
continue;
}
//確定したノード番号が-1かノードiの現時点の最小コストが小さいとき
//確定ノード番号を更新する
if( doneNode<0 || node[i].minCost < node[doneNode].minCost){
doneNode = i;
}
}
if(doneNode==-1) break; //すべてのノードが確定したら終了
node[doneNode].done = true; //ノードを確定させる
for(int i=0 ; i<node[doneNode].to.size() ; i++){
int to = node[doneNode].to[i];
int cost = node[doneNode].minCost + node[doneNode].cost[i];
//ノードtoはまだ訪れていないノード
//またはノードtoへより小さいコストの経路だったら
//ノードtoの最小コストを更新
if( node[to].minCost < 0 || cost < node[to].minCost ){
node[to].minCost = cost;
node[to].from = doneNode;
}
}
}
}
int main(){
int n;
while(1){
struct Node node[NODE_NUM];
cout << "ノードの数を入力:";
cin >> n;
if(n==0) break;
for(int i=0 ; i<n ; i++){
int m;
cout << "ノード番号" << i << "とつながっているノード数:";
cin >> m;
for(int j=0 ; j<m ; j++){
cout << "ノード番号" << i << "とつながっているノード番号とコスト:" << endl;
int cost,No;
cin >> No >>cost;
addEdge( i , No , cost , node);
}
}
//ここまででグラフに関する情報(エッジ、ノード)は構造体node[]に入っている
cout << "スタートノード&ゴールノード番号を入力:";
int start,end;
cin >> start >> end;
//ダイクストラ法で最短経路を求める
dijkstra( n , start , end , node );
//最短経路を調べる
vector<int> path;//最短経路の情報を保持するvector
//最短経路をゴールから順にスタートまでたどる
for(int i = end ; i != start ; i = node[i].from ){
path.push_back(i);
}
path.push_back(start);
//最短経路の出力
cout << "最短経路は" << endl;
for(int i = path.size()-1 ; i >= 0 ; i--){
cout << path[i] << " ";
}
cout << endl;
//最短距離
cout << node[end].minCost << endl;
}
return 0;
}
#endregion
#image(graph4.gif)
上のグラフに先ほどのダイクストラ法のプログラム(dijkstra.cpp)に適用してみます
初めにグラフの情報をいれます。
***Input
5
1
1 1
2
0 1
2 2
3
1 2
3 6
4 3
2
2 6
4 1
2
2 3
3 1
上のInputを入力することで図のグラフを構造体nodeにデータが入ります。
次にスタートノードとゴールノードの番号が聞かれているはずなので
0 3
と入力します
***Output
最短経路は
0 1 2 4 3
7
正しく最短経路と最短距離が出力されています。
なおこのプログラムはノード数入力のところで0を入力すると終了します。
あとは問題に応じてこのプログラムを多少書きかえる必要があるかと思います。
...
**ダイクストラ法
&bold(){ダイクストラ法(Dijkstra's algorithm)}とは,グラフ上の２点間の最短経路を
効率よく求めるアルゴリズムです。ただしエッジに負のコストがあると使えないアルゴリズムとなっています。
このページは[[グラフとは]]のページを見たことを前提に説明していますので、目を通してください。
このページではダイクストラ法をいかにしてC++でコーディングするかに注目するため、
ダイクストラ法のアルゴリズムの詳細は説明しません。下記のリンク先のページを見てください。
[[wikipedia>>http://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95]]
[[ACM/ICPC国内予選突破の手引き>>http://www.deqnotes.net/acmicpc/dijkstra/]]
[[グラフとは]]のページでグラフの情報を構造体として扱いましたが、
ダイクストラ法のためにメンバ変数を追加します。
struct Node{
vector<int> to; //どのノードとつながっているか
vector<int> cost; //エッジのコスト
//ここから下はダイクストラ法のために必要な情報
bool done; //確定ノードかどうか
int minCost; //スタートノードからのコスト
int from; //どのノードから来たか
};
またエッジを追加する関数は
//エッジを追加する関数
void addEdge(int v, int u, int weight, struct Node *node){
//ノードuはノードvとつながっている情報を入れる
node[ u ].to.push_back( v );
//ノードuとノードvのエッジの重みを入れる
node[ u ].cost.push_back( weight );
//有向グラフならここから下の処理が不要
//ノードvはノードuとつながっている情報を入れる
node[ v ].to.push_back( u );
//ノードvとノードuのエッジの重みを入れる
node[ v ].cost.push_back( weight );
}
この関数は[[グラフとは]]のページと同じものです。
この関数を呼び出すことで必要なエッジを追加することができます。
***ダイクストラ法のソースコード
グラフの情報がすべて構造体nodeに入っている状態で
関数dijkstra()にノード数n、スタートノードの番号start、ゴールノードの番号end、構造体node,
を渡すと最短経路を求めてくれます。
//ダイクストラ法
void dijkstra(int n, int start, int end, struct Node *node){
//変数の初期化
for(int i=0 ; i<n ; i++){
node[i].done = false;
node[i].minCost = -1;
}
node[start].minCost = 0; //スタートノードまでのコストは0
while(1){
int doneNode = -1; //最新の確定したノード番号(-1はNULLのかわり)
for(int i=0 ; i<n ; i++){
if( node[i].done==true ){//ノードiが確定しているときcontinue
continue;
}
if( node[i].minCost < 0 ){//ノードiまでの現時点での最小コストが不明のとき
continue;
}
//確定したノード番号が-1かノードiの現時点の最小コストが小さいとき
//確定ノード番号を更新する
if( doneNode<0 || node[i].minCost < node[doneNode].minCost){
doneNode = i;
}
}
if(doneNode==-1) break; //すべてのノードが確定したら終了
node[doneNode].done = true; //ノードを確定させる
for(int i=0 ; i<node[doneNode].to.size() ; i++){
int to = node[doneNode].to[i];
int cost = node[doneNode].minCost + node[doneNode].cost[i];
//ノードtoはまだ訪れていないノード
//またはノードtoへより小さいコストの経路だったら
//ノードtoの最小コストを更新
if( node[to].minCost < 0 || cost < node[to].minCost ){
node[to].minCost = cost;
node[to].from = doneNode;
}
}
}
}
&bold(){最短経路を出力したい場合には}
vector<int> path;//最短経路の情報を保持するvector
//最短経路をゴールから順にスタートまでたどる
for(int i = end ; i != start ; i = node[i].from ){
path.push_back(i);
}
path.push_back(start);
//最短経路の出力
cout << "最短経路は" << endl;
for(int i = path.size()-1 ; i >= 0 ; i--){
cout << path[i] << " ";
}
cout << endl;
上の処理を関数dijkstra()を呼び出した後にmain関数に書くといいです。
最後に余分な空白文字がでるので気をつけてください。
&bold(){最短距離を出力したい場合には}
cout << node[end].minCost << endl;
と関数dijkstra()を呼び出した後にmain関数に書いてください。
***まとめのソースコード
#region(open,ダイクストラ法のソースプログラム)
/*
* dijkstra.cpp
* by otaks , 2010-06-20
*/
#include <iostream>
#include <vector>
using namespace std;
//ノードの数
#define NODE_NUM 10
struct Node{
vector<int> to; //どのノードとつながっているか
vector<int> cost; //エッジのコスト
//ここから下はダイクストラ法のために必要な情報
bool done; //確定ノードかどうか
int minCost; //スタートノードからのコスト
int from; //どのノードから来たか
};
//エッジを追加する関数
void addEdge(int v, int u, int weight, struct Node *node){
//ノードuはノードvとつながっている情報を入れる
node[ u ].to.push_back( v );
//ノードuとノードvのエッジの重みを入れる
node[ u ].cost.push_back( weight );
//有向グラフならここから下の処理が不要
//ノードvはノードuとつながっている情報を入れる
node[ v ].to.push_back( u );
//ノードvとノードuのエッジの重みを入れる
node[ v ].cost.push_back( weight );
}
// ダイクストラ法
void dijkstra(int n, int start, int end, struct Node *node){
//変数の初期化
for(int i=0 ; i<n ; i++){
node[i].done = false;
node[i].minCost = -1;
}
node[start].minCost = 0; //スタートノードまでのコストは0
while(1){
int doneNode = -1; //最新の確定したノード番号(-1はNULLのかわり)
for(int i=0 ; i<n ; i++){
if( node[i].done==true ){//ノードiが確定しているときcontinue
continue;
}
if( node[i].minCost < 0 ){//ノードiまでの現時点での最小コストが不明のとき
continue;
}
//確定したノード番号が-1かノードiの現時点の最小コストが小さいとき
//確定ノード番号を更新する
if( doneNode<0 || node[i].minCost < node[doneNode].minCost){
doneNode = i;
}
}
if(doneNode==-1) break; //すべてのノードが確定したら終了
node[doneNode].done = true; //ノードを確定させる
for(int i=0 ; i<node[doneNode].to.size() ; i++){
int to = node[doneNode].to[i];
int cost = node[doneNode].minCost + node[doneNode].cost[i];
//ノードtoはまだ訪れていないノード
//またはノードtoへより小さいコストの経路だったら
//ノードtoの最小コストを更新
if( node[to].minCost < 0 || cost < node[to].minCost ){
node[to].minCost = cost;
node[to].from = doneNode;
}
}
}
}
int main(){
int n;
while(1){
struct Node node[NODE_NUM];
cout << "ノードの数を入力:";
cin >> n;
if(n==0) break;
for(int i=0 ; i<n ; i++){
int m;
cout << "ノード番号" << i << "とつながっているノード数:";
cin >> m;
for(int j=0 ; j<m ; j++){
cout << "ノード番号" << i << "とつながっているノード番号とコスト:" << endl;
int cost,No;
cin >> No >>cost;
addEdge( i , No , cost , node);
}
}
//ここまででグラフに関する情報(エッジ、ノード)は構造体node[]に入っている
cout << "スタートノード&ゴールノード番号を入力:";
int start,end;
cin >> start >> end;
//ダイクストラ法で最短経路を求める
dijkstra( n , start , end , node );
//最短経路を調べる
vector<int> path;//最短経路の情報を保持するvector
//最短経路をゴールから順にスタートまでたどる
for(int i = end ; i != start ; i = node[i].from ){
path.push_back(i);
}
path.push_back(start);
//最短経路の出力
cout << "最短経路は" << endl;
for(int i = path.size()-1 ; i >= 0 ; i--){
cout << path[i] << " ";
}
cout << endl;
//最短距離
cout << node[end].minCost << endl;
}
return 0;
}
#endregion
#image(graph4.gif)
上のグラフに先ほどのダイクストラ法のプログラム(dijkstra.cpp)に適用してみます
初めにグラフの情報をいれます。
***Input
5
1
1 1
2
0 1
2 2
3
1 2
3 6
4 3
2
2 6
4 1
2
2 3
3 1
上のInputを入力することで図のグラフの情報が構造体nodeにデータが入ります。
次にスタートノードとゴールノードの番号が聞かれているはずなので
0 3
と入力します
***Output
最短経路は
0 1 2 4 3
7
正しく最短経路と最短距離が出力されています。
なおこのプログラムはノード数入力のところで0を入力すると終了します。
あとは問題に応じてこのプログラムを書きかえてください。
...
表示オプション
横に並べて表示：
変化行の前後のみ表示：
