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

1、一、 概述1二、系统分析 1三、概要设计2四、详细设计54.1建立图的存储结构 54.2单源最短路径64.3任意一对顶点之间的最短路径 7五、运行与测试 812参考文献11附录交通咨询系统设计（最短路径问题）一、概述在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的 联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权 值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种 问题，例如：如何选择一条路径使得从 A城到B城途中中转次数最少； 如何选择一条路径使得从 A城到B城里程最短；如何选择一条路径使 得从A城到B

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

3、； 实现两个城市顶点之间的最短路径问题。交通咨询系统1 T立的储构 建图存结义迪杰斯特拉算法（单源最短路径）费洛依 德算法（任意 顶点对 间最短 路径）迪杰斯特拉算法流图:弗洛伊德算法流图:四、详细设计4.1建立图的存储结构定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关 系的矩阵。设G=(V,E)是具有n个顶点的图，贝S G的邻接矩阵是具有 如下定义的n阶方阵。Wj，若(Vi,Vj)或 Vi,Vj=E E(G)Ai,j“0或%其他情况注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数 组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息(下标为i

4、的元素存储顶点Vi的信息)。 邻接矩阵的存储结构：#define MVNum 100 / 最大顶点数typedef structVertexType vexsMVNum;顶点数组，类型假定为 char型Adjmatrix arcsMVNumMVNum;邻接矩阵，假定为 int 型MGraph;注：由于有向图的邻接矩阵是不对称的，故程序运行时只需要输入所有有向边及其权值即可。4.2单源最短路径单源最短路径问题：已知有向图（带权），期望找出从某个源点S V到G中其余各顶点的最短路径。迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。算法思想：设有向图G=（V,E），其中V=1,2 ,n, c

5、ost是表 示G的邻接矩阵，costij表示有向边i,j的权。若不存在有向边 i,j，则costij 的权为无穷大（这里取值为32767）。设S是一个集合， 集合中一个元素表示一个顶点，从源点到这些顶点的最短距离已经求 出。设顶点Vi为源点，集合S的初态只包含顶点M。数组dist记录 从源点到其它各顶点当前的最短距离，其初值为disti= costij , i=2 ,n。从S之外的顶点集合 V-S中选出一个顶点 w,使distw的值最小。于是从源点到达 w只通过S中的顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的 距离：从原来的distv和distw+costwv中选

6、择较小的值作为新的distv。重复上述过程，直到S中包含V中其余顶点的最短路 径。最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合， 数组dist记录了从源点到V中其余各顶点之间的最短路径，path是 最短路径的路径数组，其中pathi表示从源点到顶点i之间的最短 路径的前驱顶点。4.3任意一对顶点之间的最短路径任意顶点对之间的最短路径问题，是对于给定的有向网络图G=(V,E),要对G中任意一对顶点有序对，“V,W(VmW)”找出V到W 的最短路径。而要解决这个问题，可以依次把有向网络图中每个顶点 作为源点，重复执行前面的迪杰斯特拉算法n次，即可求得每对之间 的最短路径。费洛伊德算法的

7、基本思想：假设求从 V到V的最短路径。如果存在一条长度为arcsij的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径Vi,Vi和Vi,Vj是否存在。如果存 在，则比较路径Vi.V j和Vi,Vi,Vj的路径长度，取长度较短者为当 前所求得。该路径是中间顶点序号不大于1的最短路径。其次，考虑从Vi到Vj是否包含有顶点V2为中间顶点的路径VVi,v 2,Vj,若 没有，则说明从Vi到Vj的当前最短路径就是前一步求出的；若有， 那么Vi ,V 2,V j 可分解为VVi ,V 2和VV2,V j ，而这两条路 径是前一次找到的中间点序号不大于 1的最短路径，将这两条路径长 度相加就得

8、到路径VVi,V 2,Vj的长度。将该长度与前一次中求得 的从Vi到Vj的中间顶点序号不大于1的最短路径比较，取其长度较 短者作为当前求得的从Vi到Vj的中间顶点序号不大于2的最短路径。 依此类推直至顶点Vn加入当前从Vi到Vj的最短路径后，选出从Vi到Vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序 号不大于n,所以Vi到Vj的中间顶点序号不大于n的最短路径，已考 虑了所有顶点作为中间顶点的可能性，因此，它就是Vi到Vj的最短路径五、运行与测试徐州实例1运行结果: NW算耳直耳个数和边数八哄厂仙11 短短 虫H 有帀 到个 市两 _任1源点=12-3-13-1路径长04513911

9、36711?请选择记或2,选择晒退出=15-4-7-1&-2-3-1723687,1385 76,1385萨选择江或2,诜择印艮出: 希径嚼严.醫径长&丄2SG6957042018227413S5一任 kuK 习习2-3-1314-16-3-17-4-1卜em求城 币 之 间 最短 路径h青选择或趴选择回退岀:XX XX XX XX XX XX求城市之I El耳貳短E备彳仝XXXXXXXXKXXXt i 曇取 市间 城之 有市 MB 到个 市两 WS g 一任 f请选择=i或z,选择退岀二诫松馳鳌一7径路长度沁3*求城市之间最迈路径*W*eHHf1 短短 中可 城之 有帀 飾城 到个 市两 $

10、 一任 1请选择二1或2,选择陌退出：2输入源点（或起点）和终点3叭？朋戏顶点？至2最短路径路径是=?-4-3-2径路长度次5“六、总结与心得该课程设计主要是从日常生活中经常遇到的交通网络问题入手，进而利用计算机去建立一个交通咨询系统，以处理和解决旅客们关心 的各种问题（当然此次试验最终主要解决的问题是： 最短路径问题）。这次试验中我深刻的了解到了树在计算机中的应用是如何的神奇与灵活，对于很多的问题我们可以通过树的相关知识来解决，特别 是在解决最短路径问题中，显得尤为重要。经过着次实验，我了解到了关于树的有关算法，如：迪杰斯特拉 算法、弗洛伊德算法等，对树的学习有了一个更深的了解。参考文献【1

11、】数据结构严蔚敏.清华大学出版社.【2】数据结构课程设计苏仕华.极械工业出版社.附录#in clude#in clude#defi ne MVNum 100#define Maxi nt 32767enum boolea nFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;typedef structVertexType vexsMVNum;Adjmatrix arcsMVNumMVNum;MGraph;int D1MVNum,p1MVNum;int DMVNumMVNum,pMVNumMVNum; void CreateMGra

12、ph(MGraph * G ,int n,int e) int i,j,k,w;for(i=1;ivexsi=(char)i;for(i=1;i=n ;i+)for(j=1;jarcsij=Maxi nt;printf(输入 %d 条边的 i.j 及 w:n,e); for(k=1;karcsij=w;n);printf(有向图的存储结构建立完毕！void Dijkstra(MGraph *G ,int v1,int n)int D2MVNum,p2MVNum;int v,i,w,mi n;en um boolean SMVNum;for(v=1;varcsv1v;if(D2vMaxi nt)

13、p2v=v1;elsep2v=0;D2v1=0; Sv1=TRUE;for(i=2;i n; i+)mi n=Maxi nt;for(w=1;w=n; w+)if(!Sw & D2wmi n)v=w;mi n=D2w;Sv=TRUE;for(w=1;warcsvwarcsvw; p2w=v;printf(路径长度路径n);for(i=1;i=n; i+)prin tf(%5d,D2i);prin tf(%5d,i);v=p2i;while(v!=O)prin tf(-%d,v);v=p2v;prin tf(n);void Floyd(MGraph *G,i nt n)int i,j,k,v,w

14、;for(i=1;i=n ;i+)for(j=1;jarcsij!=Maxi nt)pij=j;elsepij=0;Dij=G-arcsij;for(k=1;k=n; k+)for(i=1;i=n ;i+)for(j=1;j=n ;j+)if(Dik+DkjDij)Dij=Dik+Dkj; pij=pik；void mai n()MGraph *G;int m, n,e,v,w,k;int xz=1;G=(MGraph *)malloc(sizeof(MGraph);printf(输入图中顶点个数和边数n ,e:);scan f(%d,%d, &n,& e);CreateMGraph(G, n,e);while(xz!=0)prin tf(*求城市之间最短路径 *、n”)；prin tf(”= n);printf(1.求一个城市到所有城市的最短路径n);printf(2.求任意的两个城市之间的最短路径n);prin tf(”= n); printf(请选择:1或2，选择0退出:n);scan f(%d，& xz);if (xz=2)Floyd(G, n);printf(输入源点(或起点)和终点:v,w:);scan f(%d,%d, &v,&w);k=pvw;