迪杰斯特拉算法
求如何将迪杰斯特拉算法的整条最短路径都输出来！不是只是输出端点和距离！迪杰斯特拉算法不行也可以用别的，不过要用C语言写的！拜谢！有点急！
用个结构体存储一下。。。比较笨的方法。。。
#include <stdio.h>
#include <stdlib.h>
int n=8;
int cost[100][100];
struct node{
int data;
int pre;
}Lnode[100];
void dijkstra(int v0,int v1)//dijkstra算法
{
int s[100];
int mindis,dis,i,j,u;
for(i=1;i<=n;i++)
{
Lnode[i].data=cost[v0][i];
s[i]=0;
}
s[v0]=1;
for(i=1;i<=n;i++)
{
mindis=32676;
for(j=1;j<=n;j++)
{
if(s[j]==0&&Lnode[j].data<mindis)
{
u=j;
mindis=Lnode[j].data;
if(Lnode[j].pre==0)
Lnode[j].pre=v0;
}
}
s[u]=1;
for(j=1;j<=n;j++)
{
if(s[j]==0)
{
dis=Lnode[u].data+cost[u][j];
if(Lnode[j].data>dis)
{
Lnode[j].data=dis;
Lnode[j].pre=u;
}
else
{
Lnode[j].data=Lnode[j].data;
}
}
}
if(i==v1)
break;
}
printf("%d到%d的最短距离：\n",v0,v1);
printf("%d ",Lnode[v1].data);
while(1)
{
printf("%d ",Lnode[v1].pre);
v1=Lnode[v1].pre;
if(v1==v0)
break;
}printf("\n");
}
int main()
{
int i,j,v0=1,v1=7,d;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cost[i][j]=32676;
}
}
for(i=1;i<=n;i++)
{
cost[i][i]=0;
}
cost[1][2]=20;cost[1][4]=50;cost[1][3]=30;
cost[2][5]=40;cost[2][8]=30;cost[3][4]=40;
cost[3][6]=20;cost[4][5]=20;cost[4][7]=90;
cost[5][7]=60;cost[5][8]=70;cost[6][4]=30;
cost[6][5]=100;cost[6][7]=80;cost[8][7]=150;
dijkstra(v0,v1);
return 0;
}
我试过了，应该可以！
