交通咨询系统设计（最短路径问题）.docx

1、3交通咨询系统设计（最短路径问题） 3.1【问题描述】在交通网络非常发达,交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。”假设图中每一站都需要换车，那么这个问题反映到图上就是要找一条从顶点A到顶点B的所含边数目最少的路径。我们只需要从顶点A出发对

2、图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径。路径上A与B之间的顶点就是路径的中转站，但这只是一类最简单的图的最短路径问题。系统还可以回答诸如此类的等等的路径选择问题。设计一个交通咨询系统，为出差、旅游或做其他出行的客人提供各种路径选择信息查询服务。3.2【设计需求及分析】设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任

3、两个城市顶点之间的最短路径问题。3.2.1建立图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n阶方阵：设G=（V，E）是一个图，结点集为。G的邻接矩阵当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下：#definf MVNum 50 /最大顶点数typedef struct VertexType vexsMVNum; /顶点数组，类型假定为c

4、har型 Adjmatrix arcsMVNumMVNum; /邻接矩阵，假定为int型MGraph;3.2.2单源最短路径最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带权），我们希望找出从某个源点SV到G中其余各顶点的最短路径。为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。迪杰斯特拉算法求最短路径的实现思想是：设G=（V，E）是一个有向图，结点集为，cost是表示G的邻接矩阵，costij表示有向边的权。若不存在有

5、向边，则costij的权为无穷大（这里取值为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含一个元素，即顶点v1。数组dist记录从源点到其他顶点当前的最短距离，其初值为disti=costv1i,i=1,2,n。从S之外的顶点集合V-S中选出一个顶点w，使distw的值最小。于是从源点到达w只通过S中顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的distv和distw+costwv中选择较小的值作为新的distv。重复上述过程，直到V-S为空。最终结果是：S记录了从源点到

6、该顶点存在最短路径的顶点集合，数组dist记录了源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中pathi表示从源点到顶点i之间的最短路径的前驱顶点。因此，迪杰斯特拉算法可用自然语言描述如下：初始化S和D，置空最短路径终点集，置初始的最短路径值；Sv1=TRUE; Dv1=0； /S集初始时只有源点，源点到源点的距离为0；While (S集中顶点数n)开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中；Sv=TRUE；更新当前最短路径及距离；3.2.3任意一对顶点间最短路径任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V，E），要对G中任意一对顶点有序

7、对“v,w(vw)”,找出v到w的最短路径。要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论的迪杰斯特拉算法n次，即可以求得每对顶点之间的最短路径。这里还可以用另外一种方法，称作费洛伊德（Floyd）算法。费洛伊德（Floyd）算法算法的基本思想是：假设求从顶点 vi到vj的最短路径。如果从vi到vj存在一条长度为arcsij的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径和是否存在。如果存在，则比较和的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径，若没

8、有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么可分解为和,而这两条路径是前一次找到的中间顶点序号不大于1的最短路径，将这两条路径长度相加就得到路径的长度。将该长度与前一次中求出的从vi到vj的中间顶点序号不大于1的最短路径比较，取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推，直到顶点vn加入当前从vi到vj的最短路径后，选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到vj的最短路径。3.3【设计功能的实现

9、】3.3.1 建立有向图的存储结构void CreateMGraph(MGraph *G,int n,int e) /构建城市的有向图 int i,j,k,x; for(i=1;ivexsi=(char)i; for(i=1;i=n;i+) for(j=1;jarcsij=Maxint; /距离初始化 printf(输入%d条边的i,j及x: n,e); for(k=1;karcsij=x; /建立城市之间的距离 printf(城市的有向图存储结构建立完毕!n); 3.3.2 迪杰斯特拉算法void Dijkstra(MGraph *G,int v1,int n) /迪杰斯特拉特拉算法求一个城

10、市到任意一个城市的距离 int D2Num,P2Num; int v,i,w,min; enum boolean SNum; for (v=1;varcsv1v; /距离初始化 if(D2vMaxint) / 路径初始化 P2v=v1; else P2v=0; P2v1=0;Sv1=TRUE; /源点V1放入s中 for(i=2;in;i+) /循环直至所有顶点的最都求出 min=Maxint; /Maxint置最小长度初值 for(w=1;w=n;w+) /选不在S中且有最小顶点w if(!Sw&D2wmin) v=w;min=D2w; Sv=TRUE; for(w=1;warcsvwarc

11、svw; P2w=v; printf(路径长度 路径n); /输出最短路径 for(i=1;i=n;i+) printf(%5d,D2i); printf(%5d,i); v=P2i; while(v!=0) printf(-%d,v); v=P2v; printf(n); 3.3.3 费洛伊德算法void Floyd(MGraph *G,int n) /用弗洛伊德算法求任意两顶点最短距离 int i,j,k; /定义三个变量 for(i=1;i=n;i+) for(j=1;jarcsij!=Maxint) /距离初始化 Pij=j; /路径初始化 else Pij=0; Dij=G-arcs

12、ij; for(k=1;k=n;k+) /以k为源点循环求出所有顶点的最短路径 for(i=1;i=n;i+) /i为已知最短路径的顶点 for(j=1;j=n;j+) /j为未知最短路径的顶点 if(Dik+DkjDij) Dij=Dik+Dkj; Pij=Pik; printf(dij=%d,pij=%dn,Dij,Pij); 3.3.4 运行主控程序#include#include #define Num 300 /定义常量Num #define Maxint 32767enum booleanFALSE,TRUE; /定义布尔型typedef char VertexType; type

13、def int Adjmatrix; typedef struct VertexType vexsNum; /定义顶点 Adjmatrix arcsNumNum; /定义路径长度 MGraph; int D1Num,P1Num; int DNumNum,PNumNum; void CreateMGraph(MGraph *G,int n,int e); /构建城市的有向图的声明 void Dijkstra(MGraph *G,int v1,int n); /迪杰斯特拉算法的声明void Floyd(MGraph *G,int n); /弗洛伊德算法的声明 void main() MGraph

14、*G; /定义有向图G int n,e,v,w,k,min; int a=1; G=(MGraph *)malloc(sizeof(MGraph); printf(输入图中顶点个数和边数n，e: ); scanf(%d,%d,&n,&e); CreateMGraph(G,n,e); while(a!=0) printf( 求城市之间的最短路径 n); printf( n); printf(1代表a，北京；2代表b，西安；3代表c，郑州；4代表d，徐州；5代表e，成都；6代表f，广州；7代表g，上海n); printf(1.求一个城市到所有城市的最短路径n); printf(2.求任意的两个城市

15、之间的最短路径n); printf(请选择: 1 或 2,选择 0 退出: ); scanf(%d,&a); if(a=2) Floyd(G,n); printf(输入源点(或称起点)和终点：v,w: ); scanf(%d,%d,&v,&w); k=Pvw; if(k=0) printf(顶点%d 到 %d 无路径!n,v,w); else printf(从顶点%d到%d的最短路径是: %d,v,w,z); while(k!=w) printf(-%d,k); k=Pkw; printf(-%d,w); printf(路径长度: %dn,Dvw); else if(a=1) printf(求

16、单源路径,输入源点 v: ); scanf(%d,&v); Dijkstra(G,v,n); printf(结束求最短路径! n); 3.4【实例测试及运行结果】3.4.1 运行实例一（求给定有向图3-1的最短路径）图3-1 一个有向图具体要求之一：求顶点到其余顶点的最短路径；分别求顶点b到顶点d之间的最短路径、顶点到顶点d之间的最短路径。3.4.2 运行实例二（求给定有向图3-2的最短路径）图3-2 一个简单的交通网络图图3-2 是一个简单的交通网络图。具体要求之一：求顶点“北京”到其余各城市之间的最短路径；并分别求“成都”到“上海”之间以及“上海”到“西安”之间的最短路径。3.5【实现提示】 根据老师提供的资料以及以前数据结构中学过的最短路径问题的相关知识进行编程，利用课本的部分代码构建框架，最后细化得到最终的程序代码。 为了简便程序，将字符型的顶点用整型代替。分别用阿拉伯数字代表字母和文字，使程序简单了很多。 我做的是有向图，没有做无向图，所以在第二个实验中出现了上海到西安无路径的情况，只能反方向求由西安到上海的最短距离，得到结果1511。程序界面有点乱，不过通过调整要比先前好很多。以后应该设计界面方面多下功夫。修改后的界面