Dijkstra算法C代码Dijkstra算法C代码
#include "stdio.h"
#include "stdlib.h"
#define M 10000
int dist[M] = {0},fa[M] = {0},visit[M] = {0};
int g[M][M] = {0};
int n,start,end;
int findmin(){
int i,flag;
int min = 987654321;
for( i = 1 ; i dist[pos] + g[pos][j] ){
dist[j] = ...
Dijkstra算法C代码
#include "stdio.h"
#include "stdlib.h"
#define M 10000
int dist[M] = {0},fa[M] = {0},visit[M] = {0};
int g[M][M] = {0};
int n,start,end;
int findmin(){
int i,flag;
int min = 987654321;
for( i = 1 ; i<= n ; i++ )
if( visit[i] == 0 && dist[i] < min && dist[i] != 0){
min = dist[i];
flag = i;
}
return flag;
}
int Dijkstra(){
int i,j,pos;
for( i = 1 ; i <= n ; i++ ){
dist[i] = g[start][i];
if( dist[i] == 123456789 )
fa[i] = i;
else
fa[i] = start;
}
visit[start] = 1;
for( i = 1 ; i <= n ; i++ ){
pos = 0;
pos = findmin();
if(pos == 0)
break;
visit[pos] = 1;
for( j = 1 ; j <= n ; j++ )
if( visit[j] == 0 && dist[j] > dist[pos] + g[pos][j] ){
dist[j] = dist[pos] + g[pos][j];
fa[j] = pos;
}
}
}
int main(){
int i,j;
int p;
scanf("%d%d%d",&n,&start,&end);
for( i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= n ; j++ ){
scanf("%d",&g[i][j]);
if( i != j && g[i][j] == 0)
g[i][j] = 123456789;
}
Dijkstra();
if( dist[end] == 123456789 )
printf("NO WAY.\n");
else{
printf("%d\n",dist[end]);
p = end;
while( fa[p]!= p ){
printf("%d --> ",p);
p = fa[p];
}
printf("%d\n",start);
}
getch();
return 0;
1. }7 2 6
2. 0 20 50 30 0 0 0
3. 20 0 25 0 0 70 0
4. 50 25 0 40 25 50 0
5. 30 0 40 0 55 0 0
6. 0 0 25 55 0 10 0 7. 0 70 50 0 10 0 0 8. 0 0 0 0 0 0 0
9. 7
10. 0 20 50 30 0 0 0 11. 20 0 25 0 0 70 0 12. 50 25 0 40 25 50 0 13. 30 0 40 0 55 0 0 14. 0 0 25 55 0 10 0 15. 0 70 50 0 10 0 0 16. 0 0 0 0 0 0 0
17. */
本文档为【Dijkstra算法C代码】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483