离散数学大作业
——利用Floyd算法计算两城市间最优路径及距离
代码在最下面
一．提出问题
在交通网络非常发达、交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从 A 城到 B 城，他希望选择一条路径最短”。设计一个程序，实现对两个城市最短路径的查询。
二．模型化
精力有限，顾及不到所有城市在地图上选取了18个城市作为图的结点，
代码实现过程用汉字比较繁琐，所以在此将18个城市标号0-17进行路径问题的计算
为了尽量体现Floyd算法的计算过程，在次假定只有结点周围的且不超过1000km的城市有有向边，边的长度设为百度地图所搜索到的最短路程，剩余的城市间距离设置为最大值5000km，即不可直接到达。
例如合肥的有向边链接了郑州、南京、武汉、南昌，虽然合肥离上海、杭州也很近，但在此为了突出Floyd算法，不赋予该两座城市之间的边，而是借助南京这个结点到达。
（人手搜索，按序号找，手敲的，真的累死我了啊啊啊啊啊啊啊）
之后通过Floyd算法计算各个城市间最短距离，并且记录路径，最后格式化输出。
三. 编程实现
1、城市代号与名字匹配结构体构建
结构体Vnode，用于存储城市名字字符串，之后再通过城市代号，达到输出汉字的效果，使呈现更明确
2、静态变量
（啃了之前写noj数据结构实验11题的老本）
int lu[maxnum][maxnum][maxnum]：第一个值设为a，第二个值设为b，第三个值设为c，a，b用于定位某个节点到某个节点，c用于记录路线，即，数组用于记录某个节点到各个节点最短路径的途经节点。
wei[maxnum][maxnum]：用于记录lu[maxnum][maxnum][maxnum]数组的路径最前端此时位于第几个位置，便于更新途径节点
3、主函数模块
函数调用关系如图
4、城市名初始化函数模块
（没选到的城市无意冒犯，全部省会弄下来我会死的😂😂，随便选了18个城市）
标号与城市名对应如图
5、路径距离初始化代码
（5000即不可直达）
6、路径初始化函数模块
路径初始都设为出发结点和到达结点，暂且不考虑不可达情况，不影响后续结果。
7、Floyd算法函数模块
for循环最里层在完成路径长度的更新同时，完成了路径途经结点的更新，是Floyd函数的进化版本。
8、检测输入结点并输出路径长度及路径模块
m记录需要求多少条路径。
temp1[maxnum],temp2[maxnum]分别记录初末结点。
格式化输出。
9、输入输出测试
先输入整数n，表示要求多少组路径
然后n行输入a b表示要求从a -> b的路径
文章来源：https://www.toymoban.com/news/detail-499675.html
四. 形成结论文章来源地址https://www.toymoban.com/news/detail-499675.html
- 成功利用Floyd算法、c语言程序实现了对18个城市之间最短路径及长度的计算以及格式化输出。
- 缺点：初始的输入因本人时间有限，没能完成将输入也改成汉字输入，所以要求两城市路径要先看城市对应代号然后输入。
- 通过这次大作业，我更加深刻地理解了离散课上所教授的Floyd算法，实现了教学合一，而不是单纯的听老师讲课或是机械地写书上的习题，老师与别的班的不同教学任务富含特色，着实令我印象深刻，感谢老师栽培。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define maxnum 20
#define maxlu 5000
typedef struct Vnode{
char name[10];
}AdjList[maxnum];
AdjList cheng;
int lu[maxnum][maxnum][maxnum];
int wei[maxnum][maxnum];
void chu()
{
strcpy(cheng[0].name,"北京");
strcpy(cheng[1].name,"天津");
strcpy(cheng[2].name,"太原");
strcpy(cheng[3].name,"西宁");
strcpy(cheng[4].name,"兰州");
strcpy(cheng[5].name,"西安");
strcpy(cheng[6].name,"郑州");
strcpy(cheng[7].name,"成都");
strcpy(cheng[8].name,"武汉");
strcpy(cheng[9].name,"合肥");
strcpy(cheng[10].name,"南京");
strcpy(cheng[11].name,"上海");
strcpy(cheng[12].name,"杭州");
strcpy(cheng[13].name,"重庆");
strcpy(cheng[14].name,"长沙");
strcpy(cheng[15].name,"南昌");
strcpy(cheng[16].name,"昆明");
strcpy(cheng[17].name,"广州");
}
// 北，天，太，西，兰，西，郑，成，武，合，南，上，杭，重，长，南，昆，广
int ans[18][18]=
{// 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,
{0,137,519,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000},
{134,0,540,5000,5000,5000,694,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000},
{502,519,0,5000,601,433,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000},
{5000,5000,5000,0,222,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000},
{5000,5000,5000,218,0,626,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000},
{5000,5000,600,5000,643,0,481,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000},
{5000,709,433,5000,5000,479,0,5000,510,566,662,5000,5000,5000,5000,5000,5000,5000},
{5000,5000,5000,5000,873,746,5000,0,5000,5000,5000,5000,5000,304,5000,5000,815,5000},
{5000,5000,5000,5000,5000,5000,513,5000,0,377,533,5000,5000,5000,5000,5000,5000,5000},
{5000,5000,5000,5000,5000,5000,569,5000,385,0,170,5000,5000,5000,5000,5000,5000,5000},
{5000,5000,5000,5000,5000,5000,5000,5000,5000,169,0,305,280,5000,5000,5000,5000,5000},//南京
{5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,308,0,178,5000,5000,5000,5000,5000},
{5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,279,177,0,5000,5000,531,5000,5000},
{5000,5000,5000,5000,5000,5000,5000,301,5000,5000,5000,5000,5000,0,888,5000,843,5000},
{5000,5000,5000,5000,5000,5000,5000,5000,333,5000,5000,5000,5000,905,0,337,5000,5000},
{5000,5000,5000,5000,5000,5000,5000,5000,342,437,5000,5000,523,5000,337,0,5000,780},
{5000,5000,5000,5000,5000,5000,5000,815,5000,5000,5000,5000,5000,836,5000,5000,0,5000},
{5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,676,780,5000,0},
};
void luchu()
{
for(int i=0;i<18;i++)
for(int j=0;j<18;j++)
wei[i][j]=1;
for(int i = 0;i < 18;i++)
{
for(int j = 0;j < 18;j++)
{
lu[i][j][wei[i][j]]=i;
wei[i][j]++;
lu[i][j][wei[i][j]]=j;
wei[i][j]++;
}
}
}
void floyd()
{
int i,j,k;
for(k = 0;k < 18;k++)
{
for(i = 0;i < 18;i++)
{
for(j = 0;j < 18;j++)
{
if(ans[i][j]>ans[i][k]+ans[k][j] )
{
ans[i][j]=ans[i][k]+ans[k][j];
int w;
for(w=1;w<wei[i][k];w++)
{
lu[i][j][w]=lu[i][k][w];
}
for(w=2;w<wei[k][j];w++)
{
lu[i][j][wei[i][k]+w-2]=lu[k][j][w];
}
wei[i][j]=wei[i][k]+wei[k][j]-2;
}
}
}
}
}
void print(int m) //待改
{
int i;
int x,y;
scanf("%d",&m);
int temp1[maxnum];
int temp2[maxnum];
for(i = 0;i < m;i++)
{
scanf("%d %d",&temp1[i],&temp2[i]);
}
printf("--------------------------------------------\n");
for(i = 0;i < m;i++)
{
printf("%s -> %s 的最优路径长%dkm，最优路径为：\n",cheng[temp1[i]].name,cheng[temp2[i]].name,ans[temp1[i]][temp2[i]]);
for(int j=1;j<maxnum;j++)
{
if(lu[temp1[i]][temp2[i]][j]!=temp2[i])
printf("%s\n",cheng[lu[temp1[i]][temp2[i]][j]].name);
else
{
printf("%s\n",cheng[lu[temp1[i]][temp2[i]][j]].name);
printf("--------------------------------------------\n");
break;
}
}
}
}
int main()
{
chu();
int m;
luchu();
floyd();
print(m);
return 0;
}到了这里，关于Floyd算法实现实际问题——18个城市间最优路线规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
