求大神教我怎么改下我写的这个程序,加一段程序,能实现最短距离的路线应该怎么走,比如我要求 A 到 C 点的最短距离,同时告诉你这个最短距离要怎么走
#include<stdio.h>#include<string.h>
#define MAX 20
char place[MAX][20]={0}; //景点的名称
char jieshao[MAX][1000]; //景点的简介
int dis[MAX][MAX]={99999}; //景点的距离
int shdis[MAX][MAX]={99999}; //任意两个景点的最短距离
int n; //总地点
int dir[MAX][MAX]={0}; //存放中间点的
int jilu[MAX]; //倒着输出地名序号
void shortdis(int dis[][MAX],int shdis[][MAX],int n)
{
int i,j,k,m=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
if(shdis[i][k]+shdis[k][j]<shdis[i][j])
{
shdis[i][j]=shdis[i][k]+shdis[k][j]; //计算两点之间的最短距离
dir[i][j]=k; //存放中间点的
}
}
void shordir(int m,int n) //求路径
{
int k;
k=0;
while(dir[m][n]!=0)
{
jilu[k]=dir[m][n];
n=dir[m][n];
k++;
}
while(k!=0)
{
k--;
printf("(%d)->",jilu[k]);
}
}
void main()
{
int i,j,ju/*距离*/,t,a,b,f;
char num[MAX]; //暂时存放字符串
n=10; //先准备10个地点
for(i=1;i<=MAX;i++) //初始化,使得所有顶点的距离为99999
for(j=1;j<=MAX;j++)
dis[i][j]=dis[j][i]=shdis[i][j]=shdis[j][i]=99999;
for(i=0;i<=MAX;i++) //初始化,使得同一个顶点的距离为0
dis[i][i]=shdis[i][i]=0; //先准备10个地点名称以及简介、距离
strcpy(place[1],"操场");strcpy(jieshao[1],"学生运动的地方");
strcpy(place[2],"凯旋门");strcpy(jieshao[2],"俗称球门,面对学生公寓");
strcpy(place[3],"综合楼");strcpy(jieshao[3],"学校领导的办公地点");
strcpy(place[4],"飞翔门");strcpy(jieshao[4],"正门,少有人烟");
strcpy(place[5],"图书馆");strcpy(jieshao[5],"学生学习以及借书的地方");
strcpy(place[6],"信息学院");strcpy(jieshao[6],"信息学院老师办公地及机房");
strcpy(place[7],"现教中心");strcpy(jieshao[7],"一个我不太了解的地方");
strcpy(place[8],"教学楼");strcpy(jieshao[8],"学生平时上课用的");
strcpy(place[9],"食品学院");strcpy(jieshao[9],"没去过=_=!");
strcpy(place[10],"鸽子广场");strcpy(jieshao[10],"有许多鸽子的地方");
dis[1][2]=dis[2][1]=shdis[1][2]=dis[2][1]=400;
dis[1][3]=dis[3][1]=shdis[1][3]=dis[3][1]=200;
dis[1][4]=dis[4][1]=shdis[1][4]=dis[4][1]=300;
dis[1][6]=dis[6][1]=shdis[1][6]=dis[6][1]=350;
dis[2][3]=dis[3][2]=shdis[2][3]=dis[3][2]=100;
dis[2][5]=dis[5][2]=shdis[2][5]=dis[5][2]=200;
dis[2][7]=dis[7][2]=shdis[2][7]=dis[7][2]=225;
dis[2][8]=dis[8][2]=shdis[2][8]=dis[8][2]=400;
dis[3][5]=dis[5][3]=shdis[3][5]=shdis[5][3]=50;
dis[3][4]=dis[4][3]=shdis[3][4]=shdis[4][3]=200;
dis[3][6]=dis[6][3]=shdis[3][6]=shdis[6][3]=125;
dis[4][6]=dis[9][4]=shdis[4][6]=shdis[9][4]=100;
dis[4][9]=dis[6][4]=shdis[4][9]=shdis[6][4]=300;
dis[5][6]=dis[6][5]=shdis[5][6]=shdis[6][5]=100;
dis[5][7]=dis[7][5]=shdis[5][7]=shdis[7][5]=50;
dis[6][9]=dis[9][6]=shdis[6][9]=shdis[9][6]=100;
dis[6][7]=dis[7][6]=shdis[6][7]=shdis[7][6]=125;
dis[7][8]=dis[8][7]=shdis[7][8]=shdis[8][7]=50;
dis[8][9]=dis[9][8]=shdis[8][9]=shdis[9][8]=300;
dis[8][10]=dis[10][8]=shdis[8][10]=shdis[10][8]=200;
dis[9][10]=dis[10][9]=shdis[9][10]=shdis[10][9]=150;
while(1)
{
for(i=1;i<=n;i++)
{
printf("(%d)号景点名称:",i);
printf("%s\n",place[i]);
}
shortdis(dis,shdis,n);
printf("\n");
printf("请输入命令:\n(0)〓 退出程序,(1)〓 查询相关信息,(2)〓 查询最短路径,(3)〓 添加景点。\n");
scanf("%d",&f);
if(f==3)
{
t=n;
while(1)
{
t++;
printf("请输入(%d)号景点的名称,-1表示结束:\n",t);
scanf("%s",num);
if(strcmp(num,"-1")==0)
break;
n=t;
strcpy(place[n],num);
getchar();
printf("请输入(%d)号景点的简介:\n",n);
gets(jieshao[n]);
printf("请输入(%d)->其他各个景点的距离,-1表示结束\n:",n);
while(scanf("%d",&i),i!=-1)
{
scanf("%d%d",&j,&ju);
dis[i][j]=dis[j][i]=shdis[i][j]=shdis[j][i]=ju;
}
}
}
else if(f==1)
{
printf("请输入序号来查询相关信息,-1表示结束\n");
while(scanf("%d",&t),t!=-1)
{
printf("(%d)号景点名称:%s\n简介:%s\n距离:\n",t,place[t],jieshao[t]);
for(i=1;i<=n;i++)
{
if(dis[t][i]==99999||dis[t][i]==0);
else
printf(" (%d)号景点->(%d)号景点:%d\n",t,i,dis[t][i]);
}
}
}
else if(f==2)
{
printf("请输入任意两个序号来查询该两个景点之间的一条最短路径,-1表示结束\n");
while(scanf("%d",&a),a!=-1)
{
scanf("%d",&b);
printf("(%d)->",a);
shordir(a,b);
printf("(%d)距离:%d\n",b,shdis[a][b]);
}
}
else if(f==0)
{
break;
}
}
printf("\n");
printf("导游结束。祝您旅游愉快!\n",n);
}