Dijkstra 算法寻找最短路径 较简易
来源：程序员人生 发布时间：2015-03-11 08:05:40 阅读次数：2344次
反正觉得比书上的代码简单多了
主要的1些核心代码还是参考上1篇博客的，觉得那篇的Dij写的不错，值得细细品味
注释的话看上篇博客，vim不知道怎样注释
#include<iostream>
using namespace std ;
const int maxint = 999 ;
const int maxnum = 100 ;
int dist[maxnum] ;
int pre[maxnum] ;
int c[maxnum][maxnum] ;
void Dij(int number , int sn ,int *dist ,int *pre , int c[maxnum][maxnum]){
bool s[maxnum] ;
for(int i = 1 ;i<= number ;i++) {
dist[i] = c[sn][i] ;
s[i] = 0 ;
if(dist [i] == maxint ){
pre[i] = 0 ;
}
else {
pre[i] = sn ;
}
}
dist [sn] = 0 ;
s[sn] = 1 ;
for(int i = 2 ;i<= number ;i++) {
int pas = maxint ;
int u = sn;
for(int j = 1 ;j<= number ;j++ )
if((!s[j]) && dist[j] <pas) {
u = j ;
pas = dist[j] ;
}
s[u] = 1 ;
for(int j = 1;j<=number ;j++) {
if((!s[j]) && c[u][j] <maxint ) {
int newdist = dist[u] +c[u][j] ;
if(newdist < dist[j]){
dist[j] = newdist ;
pre[j] = u ;
}
}
}
}
}
void SearchPath (int sour_num ,int want_num){
cout << "the best way to want_num 's distance is ";
cout << dist[want_num] ;
}
int main () {
cout << "input the number of Graph :" <<endl;
int number ;
cin >> number ;
cout << "input the line-number of Graph " <<endl ;
int line_n ;
cin >> line_n ;
int a , b ,len ;
for(int i = 1 ;i <= number ;i++) {
for( int j = 1 ;j <= number ; j++) {
c[i][j] = maxint ;
}
}
for(int i = 1 ; i <= line_n ;i++ ) {
cin >> a >> b >> len ;
if(len < c[a][b] ){
c[a][b] = len ;
c[b][a] = len ;
}
}
for(int i = 1;i <= number ;i++) {
dist[i] = maxint ;
}
for(int i = 1 ;i <= number ;i++) {
for(int j = 1; j<= number; j++) {
cout << c[i][j]<< " " ;
}
cout << endl ;
}
cout <<"use the Dij ..." <<endl ;
Dij(number , 1 , dist , pre ,c) ;
cout << "input the want_num :" <<endl ;
int want_num ;
cin >> want_num ;
SearchPath (1, want_num) ;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
