邻接矩阵求短距离.doc

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

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

2、创建和存储一个全铁路系统的有向图,并实现了对途中所有节点的遍历。程序采用迪杰斯特拉(Dijkstra)算法，实现了对图中任意两城市之间的最短距离的求解，并编写输出最短路径和所有经过的城市名。例如：输入北京到西安时，输出450km北京郑州西安呼和浩特兰州输入北京到郑州时，输出500km并输出经过相应的城市。150km750km940km240km500km550km60km50km(四)程序清单#include#include#include#defineINFINITY10000#de

3、finemax100#definelen20#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-

4、>e);for(i=0;in;i++){printf("请输入第%d个城市名称：",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);printf("终点站序号：

5、n");scanf("%s",t);printf("起始站和终点站干线长度：");scanf("%d",&w);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->edg

6、es[i][j]=w;}}voiddisplay(graph*gra){inti,j,flag=0;doublesum=0;if(!gra->vexs[0].data)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序号");pri

7、ntf("%stt%d",gra->vexs[i].data,i);if(flag)printf("t该城市不可达其他城市.");else{printf("tt可达以下城市：");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]

8、);}}flag=0;sum=0;printf("");}}}voidshortPath(graph*gra,intv0,intp[][max],intd[ma