交通咨询系统设计

3．交通咨询系统设计（最短路径问题）专业：班级：姓名：学号：完成日期：3.1【问题描述】在交通网络非常发达,交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。”假设图中每一站都需要换车，那么这个问题反映到图上就是要找一条从顶点A到顶点B的所含边数目最少的路径。我们只需要从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径。路径上A与B之间的顶点就是路径的中转站，但这只是一类最简单的图的最短路径问题。系统还可以回答诸如此类的等等的路径选择问题。设计一个交通咨询系统，为出差、旅游或做其他出行的客人提供各种路径选择信息查询服务。3.2【设计需求及分析】设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。3.2.1建立图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n阶方阵：设G=（V，E）是一个图，结点集为nvvvV,,,21。G的邻接矩阵,E,,0E,,)(,)(jijijijinnjiijnnijvvvvvvvvwaaA）或当（，或）或当（，当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下：#definfMVNum50//最大顶点数typedefstruct{VertexTypevexs[MVNum];//顶点数组，类型假定为char型Adjmatrixarcs[MVNum][MVNum];//邻接矩阵，假定为int型}MGraph;3.2.2单源最短路径最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带权），我们希望找出从某个源点SV到G中其余各顶点的最短路径。为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。迪杰斯特拉算法求最短路径的实现思想是：设G=（V，E）是一个有向图，结点集为，}v,,v,{vVn21，cost是表示G的邻接矩阵，cost[i][j]表示有向边i,j的权。若不存在有向边i,j，则cost[i][j]的权为无穷大（这里取值为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含一个元素，即顶点v1。数组dist记录从源点到其他顶点当前的最短距离，其初值为dist[i]=cost[v1][i],i=1,2,……,n。从S之外的顶点集合V-S中选出一个顶点w，使dist[w]的值最小。于是从源点到达w只通过S中顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的dist[v]和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。重复上述过程，直到V-S为空。最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中path[i]表示从源点到顶点i之间的最短路径的前驱顶点。因此，迪杰斯特拉算法可用自然语言描述如下：初始化S和D，置空最短路径终点集，置初始的最短路径值；S[v1]=TRUE;D[v1]=0；//S集初始时只有源点，源点到源点的距离为0；While(S集中顶点数n){开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中；S[v]=TRUE；更新当前最短路径及距离；}3.2.3任意一对顶点间最短路径任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V，E），要对G中任意一对顶点有序对“v,w(vw)”,找出v到w的最短路径。要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论的迪杰斯特拉算法n次，即可以求得每对顶点之间的最短路径。这里还可以用另外一种方法，称作费洛伊德（Floyd）算法。费洛伊德（Floyd）算法算法的基本思想是：假设求从顶点vi到vj的最短路径。如果从vi到vj存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径vi,v1和v1,vj是否存在。如果存在，则比较vi,vj和vi,v1,vj的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径vi,…,v2,…,vj，若没有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么vi,…,v2,…,vj可分解为vi,…v2和v2,…,vj,而这两条路径是前一次找到的中间顶点序号不大于1的最短路径，将这两条路径长度相加就得到路径vi,…,v2,…,vj的长度。将该长度与前一次中求出的从vi到vj的中间顶点序号不大于1的最短路径比较，取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推，直到顶点vn加入当前从vi到vj的最短路径后，选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到vj的最短路径。3.3【设计功能的实现】（用C或C++语言描述）#includestdio.h#includestdlib.h#defineMVNum100/*最大顶点数*/#defineMaxint35000enumboolean{FALSE,TRUE};typedefcharVertextype;typedefintAdjmatrix;typedefstruct{Vertextypevexs[MVNum];/*顶点数组，类型假定为char型*/Adjmatrixarcs[MVNum][MVNum];/*邻接矩阵，假定为int型*/}MGraph;intD1[MVNum],p1[MVNum];intD[MVNum][MVNum],p[MVNum][MVNum];/*文件名save.c*/voidCreateMGraph(MGraph*G,intn,inte){/*采用邻接矩阵表示法构造有向图G,n,e表示图的当前顶点数和边数*/inti,j,k,w;for(i=1;i=n;i++)/*输入顶点信息*/G-vexs[i]=(char)i;for(i=1;i=n;i++)for(j=1;j=n;j++)G-arcs[i][j]=Maxint;/*初始化邻接矩阵*/printf(输入%d条边的i,j及w:\n,e);for(k=1;k=e;k++){/*读入e条边,建立邻接矩阵*/scanf(%d,%d,%d,&i,&j,&w);G-arcs[i][j]=w;}printf(有向图的存储结构建立完毕！\n);}/*文件名:dijkstra.c(迪杰斯特拉算法）*/voidDijkstra(MGraph*G,intv1,intn){/*用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径p[v]及其权D[v]*//*设G是有向图的邻接矩阵，若边i,j不存在，则G[i][j]=Maxint*//*S[v]为真当且仅当v属于S，及以求的从v1到v的最短路径*/intD2[MVNum],p2[MVNum];intv,i,w,min;enumbooleanS[MVNum];for(v=1;v=n;v++){/*初始化S和D*/S[v]=FALSE;/*置空最短路径终点集*/D2[v]=G-arcs[v1][v];/*置初始的最短路径值*/if(D2[v]Maxint)p2[v]=v1;/*v1是的前趋（双亲）*/elsep2[v]=0;/*v无前趋*/}/*End_for*/D2[v1]=0;S[v1]=TRUE;/*S集初始时只有源点，源点到源点的距离为0*//*开始循环，每次求的V1到某个V顶点的最短路径，并加V到S集中*/for(i=2;in;i++){/*其余n-1个顶点*/min=Maxint;/*当前所知离v1顶点的最近距离，设初值为∞*/for(w=1;w=n;w++)/*对所有顶点检查*/if(!S[w]&&D2[w]min){/*找离v1最近的顶点w，并将其赋给v，距离赋给min*/v=w;/*在S集之外的离v1最近的顶点序号*/min=D2[w];/*最近的距离*/}/*W顶点距离V1顶点更近*/S[v]=TRUE;/*将v并入S集*/for(w=1;w=n;w++)/*更新当前最短路径及距离*/if(!S[w]&&(D2[v]+G-arcs[v][w]D2[w])){/*修改D2[w]和p2[w]，w属于V-S*/D2[w]=D2[v]+G-arcs[v][w];/*更新D2[w]*/p2[w]=v;}/*End_if*/}/*End_for*/printf(路径长度路径\n);for(i=1;i=n;i++){printf(%5d,D2[i]);printf(%5d,i);v=p2[i];while(v!=0){printf(-%d,v);v=p2[v];}printf(\n);}}/*文件名floyd.c(费洛伊德算法?/voidFloyd(MGraph*G,intn){inti,j,k;for(i=1;i=n;i++)/*设置路径长度D和路径path初值*/for(j=1;j=n;j++){if(G-arcs[i][j]!=Maxint)p[i][j]=j;/*j是i的后继*/elsep[i][j]=0;D[i][j]=G-arcs[i][j];}for(k=1;k=n;k++){{/*做K次迭代，每次均试图将顶点K扩充到当前求得的从i到j的最短路径pij上*/for(i=1;i=n;i++)for(j=1;j=n;j++){if(D[i][k]+D[k][j]D[i][j]){D[i][j]=D[i][k]+D[k][j];/*修改长度*/p[i][j]=p[i][k];}}}}voidmain(){MGraph*G;intn,e,v,w,k;intxz=1;G=(MGraph*)malloc(sizeof(MGraph));printf(输入图中顶点个数和边数n,e:);scanf(%d,%d,&n,&e);CreateMGraph(G,n,e);/*建立图的存储结构*/while(xz!=0){printf(求城市之间的最断路径\n);printf(-------------------------------\n);printf(1.求一个城市到所有城市的最短路径\n);printf(2.求任意的两个城市之间的最短路径\n);printf(--------------------------------\n);printf(请选择：