C语言迪杰斯特拉实现最短路径算法

数据结构课程设计报告----旅游咨询系统设计旅游咨询系统设计-1-目录一、需求分析................................................................................................................................-2-二、系统分析................................................................................................................................-2-三、概要设计................................................................................................................................-3-一、系统划分................................................................................................................-3-二、邻接矩阵建立流程图：........................................................................................-4-三、迪杰斯特拉算法流图..............................................................错误！未定义书签。四、详细设计................................................................................................................................-6-五、调试分析................................................................................................................................-9-一、运行结果................................................................................................................-9-二、改进设想..............................................................................................................-13-六、课设总结..............................................................................................................................-13-旅游咨询系统设计-2-旅游咨询系统设计一、需求分析在交通网络日益发达的今天，人们出行有很多种方式、路线，而如何选择符合需要的方式路线成为大家的一大难题。所以，在此我利用计算机建立一个旅游咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的路线，所带权值为两个城市间的路程、时间或车费等。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低；如何选择一条路径使得从A城到B城所用的时间最少等等的一系列问题。二、系统分析设计一个旅游咨询系统，能咨询从任何一个城市顶点到其他城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。旅客可以在同一个系统中综合考虑自己的各目标城市，选择一个最佳的旅游路线和出行方式。针对最短路径问题，在本系统中采用图的相关知识，采用了迪杰斯特拉算法，解决在实际情况中的最短路径问题，而迪杰斯特拉算法的时间复杂度为O(n2),空间复杂度为O(n)。本系统使用邻接矩阵存储无向图。其中，建立矩阵的时间复杂度为O(n2),但是利用其查找一条边的时间复杂度为O(1)。本系统中包括了利用邻接矩阵建立图的存储结构和单源最短问题两大部分，使用指针数组实现利用一个程序实现最短路径和最短时间的运算。并且本系统设置了人性化的系统提示菜单，方便使用者的使用。旅游咨询系统设计-3-三、概要设计一、系统划分该系统可以划分为三个部分：1、利用邻接矩阵建立图的存储结构；2、利用迪杰斯特拉算法解决单源最短路径问题；3、实现城市之间的最短路径问题和最短时间问题。旅游咨询系统设计-4-二、邻接矩阵建立流程图：旅游咨询系统设计-5-旅游咨询系统设计-6-四、详细设计本课程设计的源程序如下所示：#includestdio.h#includestdlib.h#defineMVNum100#defineMaxint9999/*将无穷大的数值设为9999*/typedefcharvertextype;/*建立无向图*/typedefintadjmatrix;typedefstruct{vertextypevexs[MVNum];adjmatrixarcs[MVNum][MVNum];}mgraph;mgraph*G[2];/*设置指针数组用以实现距离和时间最小值求取*/voidcity_number()/*输出城市代表序号*/{printf(*************************************************************************\n);printf(1、北京2、上海3、香港4、天津5、重庆6、澳门7、哈尔滨8、石家庄);printf(\n9、兰州10、昆明11、成都12、长春13、沈阳14、长沙15、海口16、西安);printf(\n*************************************************************************\n);}voidCreatemgraph(inta,intn,inte)/*建立无向邻接矩阵*/{inti,j,k;intw;for(i=1;i=n;i++)for(j=1;j=n;j++)if(i==j)G[a]-arcs[i][j]=0;/*邻接矩阵对角线初始值设为0*/elseG[a]-arcs[i][j]=Maxint;/*其他元素设为无穷大*/for(k=1;k=e;k++)/*读入e条边数的信息*/{printf(\n输入图中各起点终点及其权值i,j,w:);/*读入无向边及其权值*/scanf(%d,%d,%d,&i,&j,&w);G[a]-arcs[i][j]=w;G[a]-arcs[j][i]=w;}}voidDijkstra(inta,intv0,intN)/*Dijkstra算法的实现和打印*/旅游咨询系统设计-7-{enumbooleanS[MVNum];/*终点集合*/intdist[MVNum],path[MVNum];/*dist表示源点v0到图中其余顶点的最短长度，path表示其对应的路径*/inti,wmin,u,num=1,k;for(i=1;i=N;i++)/*数组dist和集合S付初值*/{dist[i]=G[a]-arcs[v0][i];/*数组dist初值为邻接矩阵*/S[i]=0;/*集合S初值设为空集*/if(dist[i]Maxint)path[i]=v0;elsepath[i]=0;}S[v0]=1;/*源点v0放入集合S中*/path[v0]=0;do{wmin=Maxint;/*wmin最小值设为无穷大*/u=v0;for(i=1;i=N;i++)if(S[i]==0)/*选择不在S中且距离最小的顶点u*/if((dist[i]wmin)&&(dist[i]!=0)){u=i;wmin=dist[i];}S[u]=1;/*把距离最小的顶点u放入集合S中*/for(i=1;i=N;i++)/*修改不在S中的顶点距离*/if(S[i]==0)if(dist[u]+G[a]-arcs[u][i]dist[i]){dist[i]=dist[u]+G[a]-arcs[u][i];path[i]=u;}num++;}while(num=N);printf(\n\t输出带权无向图的单元最短路径为:\n\t);/*打印v0到其他顶点的最短路径*/for(i=1;i=N;i++){if(S[i]==1){k=i;printf(\n\t顶点%d到%d之间的路径为:,v0,i);while(k!=v0){printf(%d--,k);/*输出后继顶点*/k=path[k];/*继续寻找下一个后继顶点*/}printf(%d,k);/*输出终点*/printf(,最短路径长度为%d\n,dist[i]);/*输出最短路径*/}elseprintf(\n\t顶点%d到%d之间没有路径！,v0,i);}旅游咨询系统设计-8-printf(\n\t求一个城市到所有城市的最短路径结束，谢谢！\n\n\t\t);}voidmain()/*旅游咨询系统*/{intn,e,v,u,i,x;intz=0;G[1]=(mgraph*)malloc(sizeof(mgraph));/*建立类型为mgraph的十字链表结构*/G[2]=(mgraph*)malloc(sizeof(mgraph));printf(****************欢迎使用旅游咨询系统****************\n);printf(输入图中顶点个数和边数n,e:);scanf(%d,%d,&n,&e);city_number();for(i=1;i=n;i++)/*输入顶点信息*/{printf(\n请输入图的所有顶点i=);scanf(%d,&x);G[1]-vexs[i]=x;/*将顶点信息输入一维数组中*/G[2]-vexs[i]=x;}printf(\n请输入距离矩阵的数值\n);Createmgraph(1,n,e);/*建立距离矩阵*/printf(\n距离矩阵建立完毕\n请输入时间矩阵的数值);Createmgraph(2,n,e);/*建立时间矩阵*/printf(\n无向图的存储结构建立完毕！\n);do{printf(\n\n\n************进行最短查询************\n);printf(=========================================\n);printf(1.求一个城市到所有城市的最短路径\n);printf(2.求一个城市到所有城市的最短时间\n);printf(3.退出\n);printf(=========================================\n);printf(请输入选择:);scanf(%d,&z);/*输入选择选择矩阵*/city_number();if(z==1){printf(\n选择1求一个城市到所有城市的最短路径\n);printf(求单源路径,输入源点v:);/*输入源点v0*/scanf(%d,&v);Dijkstra(1,v,n);/*计算最短距离*/}elseif(z==2){printf(\n选择2求一个城市到所有城市的最短时间\n);printf(求单源路径,输入源点,u:);旅游咨询系统设计