Question

采用邻接矩阵存储一个有向图，求单源点到其它顶点的最短路径。

用C++编程

Answer 1

dijkstra算法
1 源点一个集合S 其它点一个集合U
2 从U中找到离s最近的点 加入S 并且更新中U中点到s的距离
3 重复2直到U为空
#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;
}