课设-交通.docx

©/N”少火学程序设计课程设计报告学院：软件学院专业：软件工程班级学号：姓名：指导教师：王会青时间：2014年6月3.交通咨询系统设计最短路径问题专业：软件工程班级：1215班姓名：张鹏远学号:2012005391完成日期:2014/6/253.1 【问题描述】在交通网络非常兴旺,交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以答复出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。”假设图中每一站都需要换车，那么这个问题反映到图上就是要找一条从顶点A到顶点B的所含边数目最少的路径。我们只需要从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径。路径上A与B之间的顶点就是路径的中转站，但这只是一类最简单的图的最短路径问题。系统还可以答复诸如此类的等等的路径选择问题。设计一个交通咨询系统，为出差、旅游或做其他出行的客人提供各种路径选择信息查询效劳。3.21 设计需求及分析】设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径(里程)或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。本设计共分三局部，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。3.2.1建立图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n阶方设G=(V,E)是一个图，结点集为V=Wi2,，匕,G的邻接矩阵A=(%)“*“，%=（wij）nxn,当（vi,vj）或<vi,vj>EO或co,当（vi,vj）或<vi,vj>iE当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下：#definfMVNum50最大顶点数typedefstructVertexTypevexsMVNum;顶点数组，类型假定为Char型AdjmatrixarcsMVNumMVNum;邻接矩阵，假定为int型MGraph;3.2.2单源最短路径最短路径的提法很多。在这里先讨论单源最短路径问题：即有向图(带权)，我们希望找出从某个源点SV到G中其余各顶点的最短路径。为了表达方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉(Dijkstra)提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。迪杰斯特拉算法求最短路径的实现思想是：设G=(V,E)是一个有向图，结点集为,V=v,V2,v,J,cost是表示G的邻接矩阵，costij表示有向边i,j的权。假设不存在有向边i,j,那么CoStij的权为无穷大(这里取值为32767)。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点Vl为源点，集合S的初态只包含一个元素，即顶点5。数组dist记录从源点到其他顶点当前的最短距离，其初值为disti=costvi,i=l,2,no从S之外的顶点集合V-S中选出一个顶点w,使distw的值最小。于是从源点到达W只通过S中顶点，把W参加集合S中，调整dist中记录的从源点到V-S中每个顶点V的距离：从原来的distv和distw+costwv中选择较小的值作为新的distvo重复上述过程，直到V-S为空。最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组diSt记录了源点到V中其余各顶点之间的最短路径，Path是最短路径的路径数组，其中Pathi表示从源点到顶点i之间的最短路径的前驱顶点。因此，迪杰斯特拉算法可用自然语言描述如下：初始化S和D,置空最短路径终点集，置初始的最短路径值；Sv,=TRUE;Dv1=O;S集初始时只有源点，源点到源点的距离为0；While（S集中顶点数n）开始循环，每次求得巧到某个V顶点的最短路径，并加V到S集中;Sv=TRUE;更新当前最短路径及距离；3.2.3任意一对顶点间最短路径任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V,E）,要对G中任意一对顶点有序对"v,w（vw）"，找出V到W的最短路径。要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论的迪杰斯特拉算法n次，即可以求得每对顶点之间的最短路径。这里还可以用另外一种方法，称作费洛伊德（FIOyd）算法。费洛伊德（Floyd）算法算法的根本思想是：假设求从顶点Vi到Vj的最短路径。如果从V,到Vj存在一条长度为arcsij的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径V“V）和V,Vj是否存在。如果存在，那么比拟V,Vj和vbvbvj的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从V,到VJ是否包含有顶点Vz为中间顶点的路径V“,V2,Vj,假设没有，那么说明从V,到V的当前最短路径就是前一步求出的；假设有，那么Vi,，V2,Vj可分解为Vi,V2和V2,，Vj,而这两条路径是前一次找到的中间顶点序号不大于1的最短路径，将这两条路径长度相加就得到路径Qi,V2,Vj的长度。将该长度与前一次中求出的从V,到V的中间顶点序号不大于1的最短路径比拟,取其长度较短者作为当前求得的从Vi到Vj的中间顶点序号不大于2的最短路径。依此类推，直到顶点V.参加当前从Vi到Vj的最短路径后，选出从Vi到Vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n,所以Vi到V)的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是Vi到VJ的最短路径。3.31设计功能的实现】3.3.1建立有向图的存储结构voidCreateMGraph(MGraph*G,intn,inte)构建城市的有向图inti,j,k,x;for(i=l;i<=n;i+)以任意城市i出发为起点G->vexsi=(char)i;for(i=l;i<=n;i+)for(j=l;j<=n;j+)任意城市j为终点G->arcsij=Maxint;距离初始化Printf("输入为d条边的i,j及x:n”,e);for(k=l;k<=e;k+)(scanf(zz%d,%d,',&i,&j,&x);G->arcsij=x;建立城市之间的距离)Printf(“城市的有向图存储结构建立完毕!n");3.3.2迪杰斯特拉算法voidDijkstra(MGraph*G,intvl,intn)迪杰斯特拉特拉算法求一个城市到任意一个城市的距离intD2Num,P2Num;intv,i,w,min;enumbooleanSNum;for(v=l;v<=n;v+)(Sv=FALSE;D2v=G->arcsvlv;if(D2v<Maxint)P2v=vl;elseP2v=0;s置空距离初始化/路径初始化P2vl=0jSvl=TRUE;for(i=2;i<n;i+)min=Maxint;for(w=l;w<=n;w+)if(!Sw&&D2w<min)(V=w;min=D2w;Sv=TRUE;for(w=l;w<=n;w+)/源点Vl放入s中循环直至所有顶点的最都求出/Maxint置最小长度初值选不在S中且有最小顶点w顶点W参加s中if(!Sw&&(D2Ev+G->arcsvw"D2w)修改不在S中的顶点的距离D2w=D2v+G->arcsvw;P2w=v;Printf("路径长度路径n");for(i=l;i<=n;i+)printf("%5d”,D2i);Printf("%5d”,i);v=P2i;while(v!=0)printf("<-,v);v=P2v;输出最短路径Printf("n");3.3.3费洛伊德算法voidFloyd(MGraph*G,intn)(inti,j,k；for(i=l;i<=n;i+)for(j=l;j<=n;j+)(if(G->arcsij!=Maxint)Pij=j；elsePij=O;Dij=G->arcsij;)for(k=l;k<=n;k+)用弗洛伊德算法求任意两顶点最短距离定义三个变量距离初始化路径初始化以k为源点循环求出所有顶点的最短路径for(i=l;i<=n;i+)i为最短路径的顶点for(j=l;j<=n;j+)/j为未知最短路径的顶点(if(Dik+Dkj<Dij)Dij=Dik+Dkj;Pij>Pik;printf(zzdij=%d,Pij=%dn”,Dij,Pij);3. 3.4运行主控程序#include<stdio.h>#include<stdlib.h>#defineNum300定义常量NUnlttdefineMaxint32767enumbooleanFALSE,TRUE);定义布尔型typedefcharVertexType;typedefintAdjmatrix;typedefstructVertexTypevexsNum;定义顶点AdjmatrixarcsNumNum;定义路径长度MGraph;intDlNum,PlNum;intDNumNum,PNumNum;voidCreateMGraph(MGraph*G,intn,inte);构建城市的有向图的声明voidDijkstra(MGraph*G,intvl,intn);迪杰斯特拉算法的声明voidFloyd(MGraph*G,intn);弗洛伊德算法的声明voidmain()(MGraph*G;定义有向图Gintn,e,v,w,k,min;inta=l;G=(MGraph*)malloc(sizeof(MGraph);Printf(输入图中顶点个数和边数n,e:)；scanf(,%d,%d”,&n,&e);CreateMGraph(G,n,e);while(a!=0)printf求城市之间的最短路径n)；printfn)；Printf(1代表a,北京；2代表b,西安；3代表c,郑州；4代表d,徐州；5代表e,成都；6代表f,广州；7代表g,上海n)；printfl.求一个城市到所有城市的最短路径n)；printf(zz2.求任意的两个城市之间的最短路径n)；Printf(请选择：1或2,选择0退出：)；scanf(/,%dzz,&a);if(a=2)Floyd(G,n);Printf(输入源点(或称起点)和终点：v,w:)；scanf(zz%d,%dzz,&v,&w);k=Pvw;if(k=0)Printf("顶点%d到%d无路径!n,v,w);elseprintf(“从顶点%d到%d的最短路径是:,v,w,z);while(k!=w)Printf("->',k);k=Pkw;)printfC->%d,z,w);Printf("路径长度：%dn”,Dvw);elseif(a=l)Printf(“求单源路径,输入源点v:");scanf(,%dz,&v);Dijkstra(G,v,n);Printf（"结束求最短路径!n"）;）3.41实例测试及运行结果】3.4.1运行实例一（求给定有向图3-1的最短路径）图3-1一个有向图具体要求之一：求顶点。到其余顶点的最短路径；分别求顶点6到顶点d之间的最短路径、顶点到顶点d之间的最短路径。频入图中顶点个锹和边数n,e:7.10I输入10条边的起煮i,终煮j及蓝径长度X：11,7.92,1,202,3,102,4,303,5,55,4,125,7,156,5,86,7,107,3,18城市的有I代表a,北吊；2代表b,西安；3代表C州；7代表g,上海请选择：i买二金城市到预有城市的曩2包佳意面两个城币N间的霰0.,郑州,4代表a,徐州；5代表e,成都，6代表f,12工短短求单源质径.输入起点M：1路径长度路径327671半：127?.径7676,w224J<o-州S郑矍-°=-s忌三誓取Aht-Z-M市间.，城之安有市西嗨>到个弱市两睛WSM海金忌;±-任出京，o<kugJd120，弋-知力择市间4表1120入顶安西城之有市系个市两翳<1UIjy21.,上一任出京，¼wkugSE-°=-3矢矢日薯取玳海畲,弋:好举74JJ京选>%TAMW青:期间:鼎激求起点85径-&8:豆3.4.2运行实例二（求给定有向图3-2的最短路径）Ii代表a,北乐；2代表b加；7代晨g,上海请选犀0.求单源堡径,输入起点路径长度路径327671半：,西安；3代表c,郑州;4代表d,徐州；5代表e,成都；6代表f,广t口一口兰H-i,÷,ID暨取市间城之有市到个图3-2一个简单的交通网络图图3-2是一个简单的交通网络图。具体要求之一：求顶点“北京”到其余各城市之间的最短路径；并分别求“成都”到“上海”之间以及“上海”至U“西安”之间的最短路径。，'E:Debugx3.exe"救人回甲J贝总午姒利边姒n,e：7,10输入1。条边的起Ei，终热及路径长度x：1,2,25531,3,6951,4,7042,5,812235113,4,3493,6,15794,7,6515,6,23686,7,1385懈市的有I从顶点5到？的最短路径是：-858993460->6-"路径长度:3*753I求城帝之间卷谶豆路径k代表匕京;2/弋表b,西安；3代表c,关B州；4代表d,徐州；5代表e,成都；6代表f,广t''.7代表g,上海S青拣择：1.於:金城市到班有城市取曩短篇优2.主任:衡两个碳币之间的霰短商至0.退出2型质驾,期南最遥鑫具.-858993460->3->4->7路径长度：t511求城能间的翕超路径a.表代.120州S&&U关CHO，短短c0瞽取弋的的“市间.，城之安有市西i-到个物市两节蓄24海1M.,上一任出京，1!4代表d,徐州；5代表e,成都；6代表£,求城市之间的最短路径，代表a,feh7代£青选律:州塞郑1>短短松羹取M、市间;城之安西嚼>到个胡市两忌.,上一任出京，1wkugdl204代表d,徐州；S代表e,成都；6代表f,3.5【实现提示】根据老师提供的资料以及以前数据结构中学过的最短路径问题的相关知识进行编程，利用课本的局部代码构建框架，最后细化得到最终的程序代码。为了简便程序，将字符型的顶点用整型代替。分别用阿拉伯数字代表字母和文字，使程序简单了很多。我做的是有向图，没有做无向图，所以在第二个实验中出现了上海到西安无路径的情况，只能反方向求由西安到上海的最短距离，得到结果1511。程序界面有点乱，不过通过调整要比先前好很多。以后应该设计界面方面多下功夫。'E:DebugW通,exe"掘入国中顶点个数和总数n,e：2输入臻边的起点i，终点J及路径长度X：123134-三的有向瑛瑞瀛*径*-M-*-M-*-M-*-M-M-*京代t5A*120.,表T任出表成i代嚼到个市两翳金忌*,，*C少*T广-*专*市间短短日薯瓯*4g*fe:*.,*HiX>*少#.IM*4(1,海i电i-M-M-*H修改后的界面