迪杰斯特拉算法 应用
发布网友
发布时间：2022-04-28 21:24
共1个回答
热心网友
时间：2022-06-23 06:32
#include<stdlib.h>
#include<string.h>
#define True 1
#define False 0
#define max 99
typedef struct jingdian{//景点 结构体
char name[16];
char num;
}jingdian;
void jdfz(struct jingdian z[])//景点赋值
{
int n;
strcpy(z[0].name, "图书馆");//名字赋值
strcpy(z[1].name, "行政楼");
strcpy(z[2].name, "理学楼");
strcpy(z[3].name, "电子信息实验楼");
strcpy(z[4].name, "理科实验楼");
strcpy(z[5].name, "计算机实验楼");
strcpy(z[6].name, "工程实验楼");
strcpy(z[7].name, "生化实验楼");
strcpy(z[8].name, "体育场");
strcpy(z[9].name, "宿舍区");
strcpy(z[10].name, "文俊楼");
strcpy(z[11].name, "文清楼");
strcpy(z[12].name, "文新楼");
strcpy(z[13].name, "文逸楼");
strcpy(z[14].name, "演艺中心");
for (n = 0; n<15; n++){//代号赋值
z[n].num = n + 1;
}
}
void ljcx(char linjie[15][15], jingdian z[])//景点查询 函数
{
int a, b; //输入代号 用
int v;
int l;//节点数
int n, m;//循环 用
int s[20];//记录 已被确定的 最短路径长度
int path[20];//记录出发到目的i当前最短路径上i的 前驱节点
int d[20];//记录当前的最短路径 长度
int min;
int temp[20] = { 0 };
int t = 0;
int pre, i;
printf("输入出发地,目的地代号,以空格隔开:");
scanf("%d %d", &a, &b);
//printf("%d %d",a,b);//测试是否获得a b
if (a<1 || a>15 || b<1 || b>15)printf("输入错误!");//判断输入是否正确
else if (a == b)printf("你已在此处!");
else{
l = 15;
for (n = 1; n <= l; n++){//求最短路径
s[n] = False;
d[n] = linjie[a - 1][n - 1];
if (d[n]<max)path[n] = a;
else path[n] = -1;
}
s[a] = 1;//出发点 路径定义
d[a] = 0;
path[a] = -1;
for (n = 1; n<l; ++n){
v = -1;
min = max;
for (m = 1; m <= l; m++){
if (!s[m] && d[m]<min){
v = m;
min = d[m];
}
}
if (v == -1) break;
s[v] = True;
for (m = 1; m <= l; m++){
if (!s[m] && (d[v] + linjie[v - 1][m - 1]<d[m])){//有最短路径时更新前驱和长度
d[m] = d[v] + linjie[v - 1][m - 1];
path[m] = v;
}
}
}
printf("\n最短路径：\n");
pre = path[b];
for (n = 1; n<=15; n++)
printf("%d ", path[n]);
printf("\n");
while (pre != -1){ //路径倒序存入临时数组
temp[t++] = pre;
pre = path[pre];
}
//printf("11");
for (i = t - 1; i >= 0; i--){
printf("%s—>", z[temp[i] - 1].name); //倒序输出临时数组
}
printf("%s", z[b - 1].name);
printf("\n\n");
}//else 尾
}
void main()//主函数
{
int n, m; //循环用n，m
char a;
jingdian z[15];
char linjie[15][15];
for (n = 0; n<15; n++)//邻接表
for (m = 0; m<15; m++){
linjie[n][m] = max;
if (n == m + 1)linjie[n][m] = linjie[m][n] = 1;
}
linjie[9][0] = linjie[0][9] = 1;
linjie[11][1] = linjie[1][11] = 1;
for (n = 11; n<15; n++){
linjie[n][10] = linjie[10][n] = 1;
}
jdfz(z);//名字代号赋值
//for(n=0;n<15;n++){//名字代号赋值 测试
//puts(z[n].name);
//printf("%d",z[n].num);
//printf("\n");
//}
//for(n=0;n<15;n++){//邻接表 测试
//for(m=0;m<15;m++){
//printf("%d",linjie[n][m]);
//}
//printf("\n");
//}
printf("校园景点列表及其编号：\n\n");
printf("1图书馆 2行政楼 3 理学楼 4 电子信息实验楼 5 理科实验楼\n6计算机实验楼 7工程实验楼 8 生化实验楼 9 体育场 10 宿舍区\n11文俊楼 12文清楼 13 文新楼 14 文逸楼 15 演艺中心\n");
printf("===========================================================================");
printf("\n选择功能：\n1.景点介绍 2.路线查询 3.退出系统\n\n选择编号：");
a = getchar();
//putchar(a);//测试是否获得字符
if (a == '1'){//景点介绍
}
else if (a == '2'){//路径查询
ljcx(linjie, z);
}
else if (a == '3'){//退出
exit(0);
//printf("这个没显示就是结束了");//是否结束了
}
else printf("输入代号错误，请重新输入:\n");//代号错误
}
