各位快来帮帮忙 关于Dijkstra算法的

来源:百度知道 编辑:UC知道 时间:2024/06/07 11:33:13
void Dijkstra(MGraph g,int v0) //狄克斯特拉算法从顶点v0到其余各顶点的最短路径
{
int dist[MAXV],path[MAXV];
int s[MAXV];
int mindis,i,j,u,n=g.vexnum;
for (i=0;i<n;i++)
{
dist[i]=g.edges[v0][i]; //距离初始化
s[i]=0; //s[]置空
if (g.edges[v0][i]<INF) //路径初始化
path[i]=v0;
else
path[i]=-1;
}
s[v0]=1; //源点编号v0放入s中
for (i=1;i<n;i++) //循环直到所有顶点的最短路径都求出
{
mindis=INF;

for (j=0;j<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<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;
}
}
printf("输出最短路径:\n");
DisPath(dist,path,s,n,v0); //输出最短路径
}

我有个疑问,我觉得最后path[]数

楼主研究的很深入,百度HI具体讨论```

1024!
专门过来顶一瓜的!

楼主说的对,说明你在研究这个问题很好。最短路径就是是最小生成树的n-1条边!