Question

最短路Dijkstra算法怎么求起点到终点经过的路程，就是把经过的每个点都显示出来，用c和c++都可，大牛来吧

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define map 65535
int graph[101][101];
void Dijkstra(int begin,int end,int n)
{
int min;
int hash[101],path[101];
for(int i=0;i<101;i++)
{
hash[i]=1;
path[i]=map;
}
hash[begin]=0;
path[begin]=0;
while(begin!=end)
{
for(int i=0;i<=n;i++)
{
if(graph[begin][i])
{
if(path[i]>path[begin]+graph[begin][i])
path[i]=path[begin]+graph[begin][i];
}

}
min=map;int j;
for(j=1;j<=n;j++)
{

if(min>path[j]&&hash[j])
{
min=path[j];
begin=j;
}
}
printf("%d\n",begin);
hash[begin]=0;
}
printf("%d\n",path[end]);
}

int main()
{
int n,m,row,col,cost;
while(scanf("%d%d",&n,&m),m+n)
{
memset(graph,0,sizeof(graph));
while(m--)
{
scanf("%d%d%d",&row,&col,&cost);
if(graph[row][col]==0)
graph[row][col]=graph[col][row]=cost;
else if(cost<graph[row][col])
graph[row][col]=graph[col][row]=cost;
}
Dijkstra(1,n,n);
}
}

Answer 1

是要怎么显示，你的源程序里面已经可以显示经过的所有点了

追问

printf("%d\n",begin);
这一句是不对的，我要的只是从起点到终点经过的路，就像导航仪一样

追答

#include
#include
#include
#include
using namespace std;
#define map 65535
int graph[101][101];
void Dijkstra(int begin,int end,int n,int *truePath)
{
int min;
int pathId=0;
int hash[101],path[101];
for(int i=0;ipath[begin]+graph[begin][i])
{
path[i]=path[begin]+graph[begin][i];
truePath[i]=begin;//更新最短的前一个点
//coutpath[j]&&hash[j])
{
min=path[j];
begin=j;
}
}
//printf("%d\n",begin);
hash[begin]=0;
}
int k=end;
int p=2;
int tp[k+1];
//这里把路径保存到一个数组里
while(truePath[k]!=0)
{
tp[p]=truePath[k];
p++;
k=truePath[k];
}
tp[1]=end;
//倒序输出就是正确的路径
for(int i=p-1;i>=1;i--)
{
cout<<tp[i]<<endl;
}

printf("%d\n",path[end]);
}

int main()
{
int n,m,row,col,cost;
while(scanf("%d%d",&n,&m),m+n)
{
int truePath[n+1]; //保存每个点最短路径的前一个点
memset(truePath,0,sizeof(truePath));
memset(graph,0,sizeof(graph));
while(m--)
{
scanf("%d%d%d",&row,&col,&cost);
if(graph[row][col]==0)
graph[row][col]=graph[col][row]=cost;
else if(cost<graph[row][col])
graph[row][col]=graph[col][row]=cost;
}
Dijkstra(1,n,n,truePath);
}
}