Question

数据结构 C++ 迪杰斯特拉算法最短路径求补充完整。分还可以再加

#include "stdafx.h"

void MINDIST(int s[],int dist[]);

{
int temp=100000 , i, w = 2;
for(i = 2;i <= n; i++)
{
if(s[i] == 0 && cost[i] < temp)
{
temp = s[i];
w = i;
}
}
return w;
}

void SEARCH_VER(int s[],int dist[],int u)
{

}

SHORTEST_PATH(int cost[][n],int v,int n,int dist[],int path[])
{ int i,w,u,count,pos[n];
for(i=0;i<n;i++)
{ s[i]=0;
dist[i]=cost[v][i];
path[i][0]=v;
pos[i]=0;
}
s[v]=1;
count=1;
while(count<n)
{ u=MINDIST(s,dist);

s[u]=1;
path[u][++pos[u]]=u;
count++;
while(1)
{ if((w=SEARCH_VER(s,dist,u))==-1)
break;
else{

if(dist[u]+cost[u][w]<dist[w])
{ dist[w]=dist[u]+cost[u][w];
for(i=o;i<pos[u];i++)
path[w][i]=path[u][i];

}
}
}
}
}

int main(int argc, char* argv[])
{
printf("Hello World!\n");
return 0;
}

中间很长那段不要改 参数什么的都不要改；
这是我的作业。做不来了。求大神们帮忙~~
这个是北京航空航天大学的数据结构 唐发根教授版本的 最短路径问题。
MINDIST(s,dist) SEARCH_VER(s,dist,u)不要改~~
大神们 求求你们了、帮帮小弟吧。中间那段很长的代码估计有错。。

Answer 1

#include <stdio.h>
int line;//结点之间的路径数
int n ; //实际结点数，我们通过键盘输入
const int maxnum = 15; //支持的最大节点数
int cost[maxnum][maxnum] = {0}; //两点之间的直线距离,最好初始化为无穷大
int s[maxnum] = {0}; //s 判断结点是否在s集合里
int dist[maxnum]; // 表示当前点到源点的最短路径长度
int path[maxnum][maxnum];

int MINDIST(int s[],int dist[])
{
int temp=100000 , i, w = 2;
for(i = 2;i <= n; i++)
{
if(s[i] == 0 && dist[i] < temp)
{
temp = dist[i];
w = i;
}
}
return w;
}

int SEARCH_VER(int s[],int dist[],int u)
{
static int j = 0;
for(; j<=n; )
if(s[j] == 0 && cost[u][j]<100000)
{
j++;
return j-1;
}
else
{
j++;
}
return -1;

}

void SHORTEST_PATH(int cost[][maxnum],int v,int last,int dist[],int path[][maxnum])
{
int i,w,u,count,pos[maxnum];
for(i=0;i<n;i++)
{
s[i]=0;
dist[i]=cost[v][i];
path[i][0]=v;
pos[i]=0;
}
s[v]=1;
count=1;
while(count<=last)
{
u=MINDIST(s,dist);
s[u]=1;
path[u][++pos[u]]=u;
count++;
while(1)
{
if((w=SEARCH_VER(s,dist,u))==-1)
break;
else
{
if(dist[u]+cost[u][w]<dist[w])
{
dist[w]=dist[u]+cost[u][w];
for(i=0;i<pos[u];i++)
path[w][i]=path[u][i];
}
}
}
}
}

int main(int argc, char* argv[])
{
printf("请输入结点数:");
scanf("%d",&n);
printf("请输入路径数:");
scanf("%d",&line);
printf("请输入结点之间的权值\n结点1,结点2,权值\n");
int ii,jj;
for (int i = 0;i<line;i++)
{
cost[ii][jj] = 100000;
dist[i] = 100000;
scanf("%d%d%d",&ii,&jj,&cost[ii][jj]);
}
SHORTEST_PATH(cost,0,n-1,dist,path);
for (i = 0;i<n;i++)
for (int j = 0;j<n;j++)
{
printf("%d\n",path[i][j]);
}

return 0;
}
你能不能告诉我这个path是做什么用的吗？我研究了一下午，只研究了这么多，但是path是做什么用的，我真的不知道，我可以改成其他的实现方法吗？

Answer 2

数据结构有错误 需要修改