邻接矩阵求最短距离

邻接矩阵求最短距离

ID:11504622

大小:139.50 KB

页数:10页

时间:2018-07-12

邻接矩阵求最短距离_第1页
邻接矩阵求最短距离_第2页
邻接矩阵求最短距离_第3页
邻接矩阵求最短距离_第4页
邻接矩阵求最短距离_第5页
资源描述:

《邻接矩阵求最短距离》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、内蒙古工业大学信息工程学院(一)实验目的本实验的目的是通过理解图的逻辑结构和存储结构,进一步提高使用理论知识指导解决实际问题的能力。(二)实验内容1、编写生成创建一个图存储全国铁路系统的数据结构;2、编写输出遍历图中所有城市枢纽的函数;3、编写实现任意两城市之间最短铁路路程的函数;4、编写实现输出这任意两城市铁路线最短距离以及沿途比经过的铁路站点的城市。(三)实验要求1、掌握图型数据结构的机器内表示和存储;2、掌握图型结构之上的算法设计与实现;3、对迪杰斯特拉算和程序的时间复杂度、空间复杂度分析。4、掌握最短路径算法思路和实现。(四)实验设计思路实验中我采用邻接矩阵来创建和存储一个全铁路系统

2、的有向图,并实现了对途中所有节点的遍历。程序采用迪杰斯特拉(Dijkstra)算法,实现了对图中任意两城市之间的最短距离的求解,并编写输出最短路径和所有经过的城市名。例如:输入北京到西安时,输出450km北京郑州西安呼和浩特兰州输入北京到郑州时,输出500km并输出经过相应的城市。150km750km940km240km500km550km60km50km第9页内蒙古工业大学信息工程学院(四)程序清单#include#include#include#defineINFINITY10000#definemax100#definelen2

3、0#defineNULL0structvertex{intnum;chardata[len];};structgraph{intn,e;vertexvexs[max];intedges[max][max];};voidcreategraph(graph*gra){inti,j,k,w;charb[len],t[len];printf("请输入全国铁路枢纽城市个数:");scanf("%d",&gra->n);printf("请输入全部枢纽城市之间的干线数:");scanf("%d",&gra->e);for(i=0;in;i++){printf("请输入第%d个城市名称:

4、",i+1);scanf("%s",gra->vexs[i].data);gra->vexs[i].num=i;}for(i=0;in;i++)for(j=0;jn;j++)gra->edges[i][j]=INFINITY;for(k=0;ke;k++){printf("输入第%d条铁路干线的信息:",k+1);printf("起点站序号:");scanf("%s",b);第9页内蒙古工业大学信息工程学院printf("终点站序号:");scanf("%s",t);printf("起始站和终点站干线长度:");scanf("%d",&w)

5、;i=0;while(in&&strcmp(gra->vexs[i].data,b)!=NULL)i++;if(i>=gra->n){printf("输入起点的城市不正确!");exit(1);}j=0;while(jn&&strcmp(gra->vexs[j].data,t)!=NULL)j++;if(i>=gra->n){printf("输入终点的城市不正确!");exit(2);}gra->edges[i][j]=w;}}voiddisplay(graph*gra){inti,j,flag=0;doublesum=0;if(!gra->vexs[0].d

6、ata)printf("没有铁路城市信息!请先创建铁路信息.");else{printf("全国铁路枢纽城市的信息如下:");for(i=0;in;i++){for(j=0;jn;j++)sum+=gra->edges[i][j];if(((int)sum/gra->n)>=INFINITY)flag=1;printf("城市名称t序号");printf("%stt%d",gra->vexs[i].data,i);if(flag)printf("t该城市不可达其他城市.");else{printf("tt可达以下城市:");第9页内

7、蒙古工业大学信息工程学院printf("t城市名称tt序号tt铁路线距离");for(j=0;jn;j++){if(gra->edges[i][j]vexs[j].data,gra->vexs[j].num,gra->edges[i][j]);}}flag=0;sum=0;prin

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。