数据结构课程设计最短路径问题试验报告.doc

数据结构课程设计最短路径问题实验报告

一、概述0

二、系统分析0

三、概要设计

四、详细设计

5.4建立图的存储结构

5.42单源最短路径

6.43任意一对顶点之间的最短路径

五、运行与测试8参考文献附录.2交通咨询系统设计（最短路径问题）

一、概述在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。

二、系统分析设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径（里程）、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪XX算法和弗XX算法。并未本系统设置一人性化的系统提示菜单，方便使用者的使用。

二、概要设计可以将该系统大致分为三个部分：建立交通网络图的存储结构；解决单源最短路径问题；实现两个城市顶点之间的最短路径问题。

5交通咨询系统r迪杰立斯特的拉算储法（单构源最短路径）费洛依德算法（任意顶点对间最短路径）迪XX算法流图:弗XX算法流图:

四、详细设计

4.建立图的存储结构定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，贝SG的邻接矩阵是具有如下定义的n阶方阵。Wj，若(Vi,Vj)或Vi,VjE(G)Ai,j0或，其他情况注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息(下标为i的元素存储顶点V的信息)。邻接矩阵的存储结构：defineMVNum0大顶点数typedefstructVerte_Typeve_sMVNum点数组，类型假定为char型Adjmatri_arcsMVNumMVNum接矩阵，假定为int型MGraph;注：由于有向图的邻接矩阵是不对称的，故程序运行时只需要输入所有有向边及其权值即可。

4.2单源最短路径单源最短路径问题：已知有向图（带权），期望找出从某个源点SV到G中其余各顶点的最短路径。迪XX算法即按路径长度递增产生诸顶点的最短路径算法。算法思想：设有向图G=（V,E），其中V=,2,n,cost是表示G的邻接矩阵，costij表示有向边i,j的权。若不存在有向边i,j，则costij的权为无穷大（这里取值为32767）。设S是一个集合，集合中一个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点W为源点，集合S的初态只包含顶点Vi。数组dist记录从源点到其它各顶点当前的最短距离，其初值为disti=costij,i=2,n。从S之外的顶点集合V-S中选出一个顶点w,使distw的值最小。于是从源点到达w只通过S中的顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的distv和distw+costwv中选择较小的值作为新的distv。重复上述过程，直到S中包含V中其余顶点的最短路径。最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了从源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组,其中pathi表示从源点到顶点i之间的最短路径的前驱顶点。

4.3任意一对顶点之间的最短路径任意顶点对之间的最短路径问题，是对于给定的有向网络图G=(V,E),要对G中任意一对顶点有序对，“V,W(W)”找出V到W的最短路径。而要解决这个问题，可以依次把有向网络图中每个顶点作为源点，重复执行前面的迪XX算法n次，即可求得每对之间的最短路径。费XX算法的基本思想：假设求从Vi到Vj的最短路径。如果存在一条长度为arcsij的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径Vi,Vi和Vi,Vj是否存在。如果存在，则比较路径XXX和Vi,vi,Vj的路径长度，取长度较短者为当前所求得。该路径是中间顶点序号不大于的最短路径。其次，考虑从Vi到Vj是否包含有顶点V2为中间顶点的路径Vi,V2,Vj,若没有，则说明从Vi到Vj的当前最短路径就是前一步求出的；若有，那么Vi,V2,Vj可分解为VVi,V2和VV2,Vj，而这两条路径是前一次找到的中间点序号不大于的最短路径，将这两条路径长度相加就得到路径Vi,V2,Vj的长度。将该长度与前一次中求得的从Vi到Vj的中间顶点序号不大于的最短路径比较，取其长度较短者作为当前求得的从Vi到Vj的中间顶点序号不大于2的最短路径。依此类推直至顶点Vn加入当前从Vi到Vj的最短路径后，选出从Vi到Vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n,所以Vi到Vj的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是Vi到Vj的最短9路径

五、运行与测试徐州实例运行结果:实例2运行结果:頑青选扌筆江或暑选j郛退出土2062-3-it?53-7044-20__年5-2-3-22746-3-3557-4-_JtH_MKKKJI__H下市丁可备彳仝S.曇取的的帀间萝有市到个市两H忌_任i请选择：或氛选择0退出:址宦址址址7瓦站市一匚司乍备卜K_K__KW___KH馬歸競髓青选择M或鮎选择D退岀;=54-7径路长度哟K恺乂址比址恺乂说覺乂社求城审N可最短各彳仝乂貳覺乂_乂刃5（i短短B取的的巾间城N有市到个市两请选择江或2,选择0退出：2输入源点（或起点租终点=u,ut

7.2川顶点？至2最短路径路径是43-2径路长度汀弓

六、总结与心得该课程设计主要是从日常生活中经常遇到的交通网络问题入手，进而利用计算机去建立一个交通咨询系统，以处理和解决旅客们关心的各种问题（当然此次试验最终主要解决的问题是：最短路径问题）。这次试验中我深刻的了解到了树在计算机中的应用是如何的神奇与灵活，对于很多的问题我们可以通过树的相关知识来解决，特别是在解决最短路径问题中，显得尤为重要。经过着次实验，我了解到了关于树的有关算法，女口：迪XX算法、弗XX算法等，对树的学习有了一个更深的了解。参考文献

数据结构严蔚敏.清华大学出版社.

【2】数据结构课程设计XXX.附录XXX.hdefineMVNum00defineMa_int32767enumbooleanFALSE,TRUE;typedefcharVerte_Type;typedefintAdjmatri_;typedefstructVerte_Typeve_sMVNum;Adjmatri_arcsMVNumMVNum;MGraph;intDMVNum,pMVNum;intDMVNumMVNum,pMVNumMVNum;voidCreateMGraph(MGraph_G,intn,inte)inti,j,k,w;for(i=;i=n;i+)G-ve_si=(char)i;for(i=;i=n;i+)for(j=;j=n;j+)G-arcsij=Ma_int;printf(输入%d条边的i.j及w:n,for(k=;k=e;k+)scanf(%d,%d,%d,i,j,w);G-arcsij=w;n);printf(有向图的存储结构建立完毕！voidDijkstra(MGraph_G,intv,intn)intD2MVNum,p2MVNum;intv,i,w,min;enumbooleanSMVNum;for(v=;v=n;v+)Sv=FALSE;D2v=G-arcsvv;if(D2vMa_int)p2v=v;elsep2v=0;D2v=0;Sv=TRUE;for(i=2;in;i+)min=Ma_int;for(w=;w=n;w+)if(!SwD2wmin)v=w;min=D2w;Sv=TRUE;for(w=;w=n;w+)if(!Sw(D2v+G-arcsvwD2w)D2w=D2v+G-arcsvw;p2w=v;printf(路径长度路径n);for(i=;i=n;i+)printf(%5d,D2i);printf(%5d,i);v=p2i;while(v!=0)printf(-%d,v);v=p2v;printf(n);voidFloyd(MGraph_G,intn)inti,j,k,v,w;for(i=;i=n;i+)for(j=;j=n;j+)if(G-arcsij!=Ma_int)pij=j;elsepij=0;Dij=G-arcsij;for(k=;k=n;k+)for(i=;i=n;i+)for(j=;j=n;j+)if(Dik+DkjDij)Dij=Dik+Dkj;pij=pik;voidmainMGraph_G;intm,n,e,v,w,k;int_z=;G=(MGraph_)malloc(sizeof(MGraph);printf(输入图中顶点个数和边数n,e:);scanf(%d,%d,n,e);CreateMGraph(G,n,e);while(_z!=0)printf(_求城市之间最短路_n);printf(=n);printf

1.求一个城市到所有城市的最短路径n);printf

2.求任意的两个城市之间的最短路径n);printf(==n);printf(请选择:或2,选择0退出:n);scanf(%d,_z);if(_z=2)Floyd(G,n);printf(输入源点(或起点)和终点:v,w:);scanf(%d,%d,v,w);k=pvw;if(k=0)printf(顶点%d到%d无路径!n,v,w);elseprintf(从顶点%d到%d最短路径路径是:%d,v,w,v);while(k!=w)printf(-%d,k);k=pkw;printf(-%d,w);printf(径路长度:%dn,Dvw);elseif(_z=)printf(求单源路径，输入源点v:);scanf(%d,v);Dijkstra(G,v,n);printf(结束求最短路径，再见!n);9