Question

dijkstra算法求该源顶点到其它所有顶点的最短路径和最短路径长度,并输出。用无向网邻接表存储结构。C语言

Answer 1

#include<stdio.h>
#define N 100
#define MaxDist 10000
int mapdist[N][N];
int mindist[N];
void Dijkstra(int n,int c)
{
int i,tag[N],minc,t,j;
for(i=1;i<=n;++i)
{
if(mapdist[c][i]>=0)
mindist[i]=mapdist[c][i];
else
mindist[i]=MaxDist;
tag[i]=0;
}
for(j=1;j<=n;++j)
{
minc=MaxDist;
for(i=1;i<=n;++i)
{
if(minc>mindist[i])
{
minc=mindist[i];
t=i;
}
}
tag[t]=1;
for(i=1;i<=n;++i)
{
if((mindist[i]>mindist[t]+mapdist[t][i])&&(!tag[i]))
mindist[i]=mindist[t]+mapdist[t][i];

}
}

}
int main()
{
int i,j,n,c;
scanf("%d%d",&n,&c);//c为源点
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
scanf("%d",&mapdist[i][j]);//-1表示不直接连通
}
Dijkstra(n,c);
for(i=1;i<=n;++i)
printf("%d",mindist[i]);
return 0;
}