#include <stdio.h>
#define MAXN 100
#define inf 1000.0
double dist[MAXN];
int p[MAXN];
void dijk(int u, double C[MAXN][MAXN], int n){
bool s[MAXN] = {false};
for(int i = 0; i < n; i++){
dist[i] = C[u][i];
if(dist[i] >= inf) p[i] = -1;
else p[i] = u;
}
dist[u] = 0;
s[u] = true;
for(int i = 0; i < n; i++){
double tmp = inf;
int t = u;
for(int j = 0; j < n; j++)
if(!(s[j]) && (dist[j] < tmp)){
t = j;
tmp = dist[j];
}
if(t == u) break;
s[t] = true;
for(int j = 0; j < n; j++)
if(!(s[j]) && (C[t][j] < inf) && (dist[j] > dist[t] + C[t][j])){
dist[j] = dist[t] + C[t][j];
p[j] = t;
}
}
}
int main(){
double C[MAXN][MAXN];
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
scanf("%lf", C[i]+j);
dijk(0, C, n);
for(int i = 0; i < n; i++)
printf("%.4f\t", dist[i]);
printf("\n");
for(int i = 0; i < n; i++)
printf("%d\t", p[i]);
return 0;
}
Dijkstra
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 前言： 一直对于最短路径算法比较好奇，适用的场景非常多，类似地铁，封闭室内，开阔的园区等场景，在给定了几个确定节点...
- dijkstra算法介绍：即迪杰斯特拉算法，是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。...
