邻接矩阵求最短距离.doc

内蒙古工业大学信息工程学院（一）实验目的本实验的目的是通过理解图的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。（二）实验内容 1、编写生成创建一个图存储全国铁路系统的数据结构；2、编写输出遍历图中所有城市枢纽的函数；3、编写实现任意两城市之间最短铁路路程的函数；4、编写实现输出这任意两城市铁路线最短距离以及沿途比经过的铁路站点的城市。(三）实验要求1、掌握图型数据结构的机器内表示和存储；2、掌握图型结构之上的算法设计与实现；3、对迪杰斯特拉算和程序的时间复杂度、空间复杂度分析。4、掌握最短路径算法思路和实现。(四)实验设计思路 实验中我采用邻接矩阵来创建和存储一个全铁路系统的有向图,并实现了对途中所有节点的遍历。程序采用迪杰斯特拉(Dijkstra)算法，实现了对图中任意两城市之间的最短距离的求解，并编写输出最短路径和所有经过的城市名。例如：输入北京到西安时，输出450km北 京郑 州西 安呼和浩特 兰 州 输入北京到郑州时，输出500km 并输出经过相应的城市。 150km 750km 940km 240km 500km 550km 60km 50km(四)程序清单#include#include#include#define INFINITY 10000#define max 100#define len 20#define NULL 0struct vertexint num;char datalen;struct graphint n,e;vertex vexsmax;int edgesmaxmax;void creategraph(graph *gra)int i,j,k,w;char blen,tlen;printf(请输入全国铁路枢纽城市个数:n); scanf(%d,&gra-n);printf(请输入全部枢纽城市之间的干线数:n);scanf(%d,&gra-e);for(i=0;in;i+)printf(请输入第%d个城市名称：n,i+1);scanf(%s,gra-vexsi.data);gra-vexsi.num=i;for(i=0;in;i+)for(j=0;jn;j+)gra-edgesij=INFINITY;for(k=0;ke;k+)printf(输入第%d条铁路干线的信息：n,k+1);printf(起点站序号：n);scanf(%s,b);printf(终点站序号：n);scanf(%s,t);printf(起始站和终点站干线长度：); scanf(%d,&w);i=0;while(in&strcmp(gra-vexsi.data,b)!=NULL)i+;if(i=gra-n)printf(输入起点的城市不正确！n);exit(1);j=0; while(jn&strcmp(gra-vexsj.data,t)!=NULL)j+;if(i=gra-n)printf(输入终点的城市不正确！n);exit(2);gra-edgesij=w;void display(graph *gra)int i,j,flag=0;double sum=0;if(!gra-vexs0.data)printf(没有铁路城市信息!请先创建铁路信息.n);elseprintf(全国铁路枢纽城市的信息如下：n);for(i=0;in;i+) for(j=0;jn;j+) sum+=gra-edgesij;if(int)sum/gra-n)=INFINITY)flag=1;printf(城市名称t序号n);printf(%stt%dn,gra-vexsi.data,i );if(flag)printf(t该城市不可达其他城市.n); elseprintf(tt可达以下城市：n);printf(t城市名称tt序号tt铁路线距离n);for(j=0;jn;j+)if(gra-edgesijvexsj.data,gra-vexsj.num,gra-edgesij);flag=0;sum=0;printf(n); void shortPath(graph *gra,int v0,int pmax,int dmax) int v,w,i,j,min; int finalmax; for(v = 0;vn;v+) finalv=0;dv=gra-edgesv0v;for(w =0;wmax;w+) pvw=-1; if (dvINFINITY) pv0=v0; pv1=v; dv0=0; finalv0=1;for(i=1;in;i+) min=INFINITY;for(w=0;wn;w+) if(!finalw) if(dwmin) v=w; min=dw; finalv=1; for(w=0;wn;w+) if(!finalw&(min+gra-edgesvwedgesvw;for(j=0;pvj-1&jn;j+) pwj=pvj; pwj = w; void findpath(graph *gra)int i,j,v0,vend,flag1=0,flag2=0;int dmax,pmaxmax;char scitylen,ecitylen;printf(输入铁路起始站城市名称：n); scanf(%s,scity);printf(输入铁路终止站城市名称：n); scanf(%s,ecity); for(i=0;in;i+)if(strcmp(gra-vexsi.data,scity)=NULL)v0=gra-vexsi.num;flag1=1;if(strcmp(gra-vexsi.data,ecity)=NULL)vend=gra-vexsi.num;flag2=1;if(flag1=NULL)printf(输入的起始站错误！);exit(1);if(flag2=NULL)printf(输入的终止站错误！);exit(2);elseshortPath(gra,v0,p,d);for(i=0;in;i+)if(i=vend)if(di=INFINITY)printf(从%s到%s不可达！n,gra-vexsv0.data,gra-vexsvend.data);elseprintf(从%s城市出发到%s城市最短路径经过的城市为:n,gra-vexsv0.data,gra-vexsvend.data);if(piv0-1)for(j=0;pij!=-1;j+)if(j!=0)printf(-);printf(%5s,gra-vexspij.data); printf(n); printf(最短路径长为:%ld(km)n,di);printf(n);int main()graph gra;char ch;doprintf(n);printf(欢迎使用铁路查询系统 n);printf( 请选择下面操作 n);printf( 1.创建铁路系统 2.查看全部铁路信息 n);printf( 3.任意两城市铁路信息查询 4.退出铁路系统 n);printf(nt);scanf(%c,&ch);switch(ch)case 1: creategraph(&gra);getchar();break;case 2: display(&gra);getchar();break;case 3: findpath(&gra);getchar();break;case 4:printf(