Question

你好，请问您能不能给我一份可以实现的迪杰斯特拉算法的C语言代码，我想求最短路径。谢谢

网上找的错误太多，自己又是个菜鸟，根本改不出来。麻烦你了

Answer 1

void Dijkstra(MGraph g,int v)
{
int dist[MAXV],path[MAXV];
int s[MAXV];
int mindis,i,j,u;
for (i=0;i<g.n;i++)
{
dist[i]=g.edges[v][i]; /*距离初始化*/
s[i]=0; /*s[]置空*/
if (g.edges[v][i]<INF) /*路径初始化*/
path[i]=v;
else
path[i]=-1;
}
s[v]=1;path[v]=0; /*源点编号v放入s中*/
for (i=0;i<g.n;i++) /*循环直到所有顶点的最短路径都求出*/
{
mindis=INF; /*mindis置最小长度初值*/
for (j=0;j<g.n;j++) /*选取不在s中且具有最小距离的顶点u*/
if (s[j]==0 && dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
s[u]=1; /*顶点u加入s中*/
for (j=0;j<g.n;j++) /*修改不在s中的顶点的距离*/
if (s[j]==0)
if (g.edges[u][j]<INF && dist[u]+g.edges[u][j]<dist[j])
{
dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
Dispath(dist,path,s,g.n,v); /*输出最短路径*/
}

试一下看能用不能、、、、、、