迪杰斯特拉问题
#include<stdio.h>#define max 20/*定义最大顶点个数*/
#define up 10000/*定义一个无穷大的值*/
#define ok 0
int cost[max][max];
int dist[max],n;/*能帮忙解释一下这里的dist[max],n表示什么吗？*/
struct
{
int num;/*这里的num,pnode[max]又表示什么*/
int pnode[max];
}path[max];
void creategraph()/*创建无向图*/
{
int i,j,s,e,len,contin=1;
printf("顶点个数:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cost[i][j]=cost[j][i]=up;
cost[i][i]=0;
printf("%5d ",cost[i][j]);
}
printf("\n");
}
printf("输入顶点，顶点，各边，以0，0,0表示结束:\n");
i=1;
while(contin==1)
{
printf("第%d条边-顶点，顶点，边长:",i);
scanf("%d %d %d",&s,&e,&len);
if(s==0&&e==0&&len==0)
contin=0;
else if(s>=0&&s<n&&e>=0&&e<n&&len>0)
{
cost[s][e]=len;
i++;
}
else
printf("边值错误，请重新输入:\n");
}
}
void shortdjs()/*迪杰斯特拉最短路径算法*/
{
int s[max];
int mindis,dis,i,j,v0=0,u;
for(i=0;i<n;i++)
{
dist[i]=cost[v0][i];
path[i].pnode[0]=v0;
path[i].num=0;
s[i]=0;
}
s[v0]=1;
for(i=0;i<n;i++)
{
mindis=up;
for(j=1;j<n;j++)
if(s[j]==0&&dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
s[u]=1;
for(j=1;j<n;j++)
if(s[j]==0)
{
dis=dist[u]+cost[u][j];
if(dist[j]>dis)
{
dist[j]=dis;
path[j].num++;
path[j].pnode[path[i].num]=i;
}
}
path[i].num++;
path[i].pnode[path[i].num]=i;
}
}
void dispath()/*最短路径输入*/
{
int i,j;
printf("\n 从v0到各顶点的最短路径长度如下:\n");
printf("********起点-终点********最短长度********最短路径\n");
for(i=1;i<n;i++)
{
printf(" (v0-v%d)",i);
if(dist[i]<up)
printf(" %d (",dist[i]);
else
printf("(");
for(j=0;j<path[i].num;j++)
printf("v%d,",path[i].pnode[j]);
printf("v%d)\n",path[i].pnode[path[i].num]);/*??????????????这里的这里两个为什么这么输出啊???????*/
}
}
int main(void)/*主程序入口*/
{
creategraph();
shortdjs();
dispath();
return ok;
}
