前端之家收集整理的这篇文章主要介绍了
最短路径问题(Dijkstra算法),
前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x6fffffff
using namespace std;
const int maxn = 10010;
int map[maxn][maxn];
int dist[maxn];
int pre[maxn];
int s;
int n;
bool p[maxn];
void Dijkstra(){
int i,j,k;
int min;
for(i = 1; i <= n; i++){
p[i] = false;
if(i != s ){
dist[i] = map[s][i];
pre[i] = s;
}
}
dist[s] = 0;
p[s] = true;
for(i = 1; i <= n-1; i++){
min = INF;
k = 0;
for(j = 1; j <= n; j++){
if(!p[j] && dist[j] < min){
min = dist[j];
k = j;//在Vb中取一点K
}
}
if(k == 0){ return ;}
p[k] = true;
printf("dist[%d] = %d\n",k,dist[k]);
for(j = 1; j <= n; j++){
if(!p[j] && map[k][j] != INF &&dist[j] > dist[k] +map[k][j]){
dist[j] = dist[k] + map[k][j];
pre[j] = k;
}
}
}
}
int work(){
int tal = 0;
for(int i = 1; i <= n; i++){
if(p[i] == true){
tal += dist[i];
}
}
return tal;
}
void init(){
memset(pre,sizeof(pre));
memset(dist,sizeof(dist));
memset(p,false,sizeof(p));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
map[i][j] = 0;
}
}
}
int main()
{
while(scanf("%d",&n) != EOF){
init();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
scanf("%d",&map[i][j]);
if(map[i][j] == 0){ map[i][j] = INF; }
}
}
printf("please input the source :\n");
scanf("%d",&s);
Dijkstra();
int res = work();
printf("The total length is %d\n",res);
}
return 0;
}
/***************
测试数据:
6
0 2 1 4 0 0
2 0 3 0 0 0
1 3 0 2 4 6
4 0 2 0 0 0
0 0 4 0 0 1
0 0 6 0 1 0
1
************/