Dijkstraアルゴリズムシミュレーションの説明
6250 ワード
dijkstraアルゴリズムは、単一ソースを求める最短パスアルゴリズムです.
アルゴリズムの特徴は次のとおりです.
幾重にも迫っていて、幅検索のような感じがします
必要なデータ構造は、int map[N][N]のすべての点の間の重みテーブルint dis[N]のすべての点からソース点までの最短距離int prev[N]が各点の前に通過した点を格納し、出力経路int用used[N]最短経路を求めた点を記憶するための総点からused中の点を減算し、最短経路がまだ見つからない点の初期化時:mapは実際の記憶の重みであり、どちらか一方がない場合は無限大INFとし、自分で0 disをソースポイントからそのポイントまでの距離に設定し、ない場合は無限大INF prevに設定し、ソースポイントに隣接する場合はソースポイントに設定し、そうでない場合は0 usedでソースポイントを除いて、残りはすべて0で初めてソースポイントからその隣接するポイントを比較し、最短距離のポイントkを見つけてused[k]=1に加える.kに隣接する点jからソース点までの距離を比較し、(dis[k]+map[k][j])ソース点からk+kからj点までの距離よりも大きい場合、dis[j]=dis[k]+map[k][j]を更新し、prev[j]=kを記録し、jの前の通過点がkであることを示し、残りの点からソース点までの最短距離を繰り返し探す.見つけた点をusedに追加し、すべてのノードがusedに追加されるまで最短パスが完了します.
具体的には、次のようになります.
アルゴリズムの特徴は次のとおりです.
幾重にも迫っていて、幅検索のような感じがします
必要なデータ構造は、int map[N][N]のすべての点の間の重みテーブルint dis[N]のすべての点からソース点までの最短距離int prev[N]が各点の前に通過した点を格納し、出力経路int用used[N]最短経路を求めた点を記憶するための総点からused中の点を減算し、最短経路がまだ見つからない点の初期化時:mapは実際の記憶の重みであり、どちらか一方がない場合は無限大INFとし、自分で0 disをソースポイントからそのポイントまでの距離に設定し、ない場合は無限大INF prevに設定し、ソースポイントに隣接する場合はソースポイントに設定し、そうでない場合は0 usedでソースポイントを除いて、残りはすべて0で初めてソースポイントからその隣接するポイントを比較し、最短距離のポイントkを見つけてused[k]=1に加える.kに隣接する点jからソース点までの距離を比較し、(dis[k]+map[k][j])ソース点からk+kからj点までの距離よりも大きい場合、dis[j]=dis[k]+map[k][j]を更新し、prev[j]=kを記録し、jの前の通過点がkであることを示し、残りの点からソース点までの最短距離を繰り返し探す.見つけた点をusedに追加し、すべてのノードがusedに追加されるまで最短パスが完了します.
具体的には、次のようになります.
/*
Filename:dijkstra.cpp
Author: xiaobing
E-mail: [email protected]
Date: 2013-08-30
*/
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<string.h>
#include<stack>
#define N 50
#define M 50
#define INF 0xfffffff
using namespace std;
/*
*dijkstra ，
:
，
:
int map[N][N]
int dis[N]
int prev[N] ，
int used[N]
used ，
：map ， ， INF, 0
dis ， ， INF
prev， ， ， 0
used ， 0
， k， used[k] = 1;
k j ， (dis[k] + map[k][j]) k + k
j ， dis[j] = dis[k] + map[k][j]， prev[j] = k,
j k， ，
used ， used ， 。
*/
/*
*dijkstra
*@node
*@from
*@map
*@dis
*@prev
*/
void dijkstra(int node, int from, int map[][N], int dis[], int prev []){
int i,j,k;
//
int used[N] = {0};
// ，
used[from] = 1;
//
for(i = 1;i <= node;i++){
dis[i] = map[from][i];
// ， 0
// from
if(dis[i] == INF || dis[i] == 0){
prev[i] = 0;
} else {
prev[i] = from;
}
}
int min;
// node ，
for(i = 1;i <= node;i++){
//
min = INF;
// used ， k
for(j = 1;j <= node;j++){
if(!used[j] && dis[j] < min){
min = dis[j];
k = j;
}
}
// used ，
used[k] = 1;
// k
// k j ， dis[j]( j )
// k + k j , :dis[k] + map[k][j]
// j k
for(j = 1;j <= node;j++){
if(dis[j] > dis[k] + map[k][j]){
dis[j] = dis[k] + map[k][j];
prev[j] = k;
}
}
}
}
//
void print(int table[][M], int row, int col){
int i,j;
for(i = 0;i < row;i++){
for(j = 0;j < col;j++){
cout<<table[i][j]<<" ";
}
cout<<endl;
}
}
// , ，
//from
//to
//prev
void printPath(int from, int to, int prev[]){
stack<int> path;
//
path.push(to);
// ， ， ， 0
// ， ， ，
while(prev[to] != 0){
path.push(prev[to]);
to = prev[to];
}
// ，
if(path.top() != from){
cout<<" "<<endl;
return ;
}
cout<<" : ";
int flag = 0; //
while(!path.empty()){
if(flag)
cout<<"->";
flag = 1;
cout<<path.top();
path.pop();
}
cout<<endl;
}
int main(){
int i, j;
//
int map[N][M];
// map INF
for(i = 0;i < N;i++){
for(j = 0;j < M;j++){
map[i][j] = INF;
if(i == j){
map[i][j] = 0;
}
}
}
//print(map, N, M);
//node
//line
//start
int node,line,start;
cin>>node;
cin>>line;
cin>>start;
int from, to,len;
// map
for(i = 0;i < line;i++){
cin>>from>>to>>len;
map[from][to] = len;
}
cout<<endl;
cout<<" :"<<endl;
print(map, node + 1, node + 1);
cout<<endl;
// 0, 0
int dis[N] = {0};
int prev[N] = {0};
dijkstra(node, start, map, dis, prev);
for(i = 0;i <= node;i++){
cout<<prev[i]<<" ";
}
cout<<endl;
cout<<" "<<start<<" :"<<endl;
for(i = 1;i <= node;i++){
cout<<start<<"--"<<i<<" ："<<dis[i]<<endl;
printPath(start, i, prev);
}
return 0;
} ：
5
7
1
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
:
0 268435455 268435455 268435455 268435455 268435455
268435455 0 10 268435455 30 100
268435455 268435455 0 50 268435455 268435455
268435455 268435455 268435455 0 268435455 10
268435455 268435455 268435455 20 0 60
268435455 268435455 268435455 268435455 268435455 0
0 0 1 4 1 3
1 :
1--1 ：0
: 1
1--2 ：10
: 1->2
1--3 ：50
: 1->4->3
1--4 ：30
: 1->4
1--5 ：60
: 1->4->3->5
=====================================
5
7
5
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
:
0 268435455 268435455 268435455 268435455 268435455
268435455 0 10 268435455 30 100
268435455 268435455 0 50 268435455 268435455
268435455 268435455 268435455 0 268435455 10
268435455 268435455 268435455 20 0 60
268435455 268435455 268435455 268435455 268435455 0
0 0 0 0 0 0
5 :
5--1 ：268435455
5--2 ：268435455
5--3 ：268435455
5--4 ：268435455
5--5 ：0
: 5
=====================================
:
0 268435455 268435455 268435455 268435455 268435455
268435455 0 40 10 268435455 268435455
268435455 268435455 0 10 30 50
268435455 268435455 80 0 20 40
268435455 268435455 268435455 268435455 0 10
268435455 268435455 268435455 268435455 268435455 0
0 0 0 2 2 4
2 :
2--1 ：268435455
2--2 ：0
: 2
2--3 ：10
: 2->3
2--4 ：30
: 2->4
2--5 ：40
: 2->4->5