数据结构实验报告五最短路径

《数据结构实验报告五最短路径》由会员分享，可在线阅读，更多相关《数据结构实验报告五最短路径（20页珍藏版）》请在装配图网上搜索。

1、计科系实验报告实验课程名称数据结构课程设计专业班级学生姓名学 号指导教师2012至2013学年第 一 学期第1至9周目录一、概述：31.1问题描述31.2系统实现的目标31.3系统实现方案3二、系统分析：42.1设计思想42.2设计要求42.3需求分析42.4算法描述5三、概要设计：73.1程序流程图8四、详细设计：94.1建立图的存储结构94.2单源最短路径94.3任意一对顶点间最短路径104.4建立有向图的存储结构114.5迪杰斯特拉算法114.6弗洛伊德算法124.7运行主控程序13五、运行与测试：14六、：总结与心得16附录：程序代码16一、概述:1.1问题描述在交通网络非常发达，交通

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

3、上，从根顶点A到顶点B 的路径就是中转次数最少的路径。路径上A与B之间的顶点就是路径的中转站， 但这只是一类最简单的图的最短路径问题。系统还可以回答诸如此类的等等的路 径选择问题。1.2系统实现的目标通过进行课程设计，了解并初步掌握设计、实现较大系统的完整过程，包括： 系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设 计、实现以及操作方法，为进一步的应用开发打好基础。应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写 程序求解指定问题。1.3系统实现方案首先确定系统要实现怎样的目的，实现这些目的需要先实现哪些程序，这就 是核心部分，划分出模块并写出其源代码

4、，此程序大致分了六大模块，由一个主 函数组和五个自定义函数组成，而后是上机调试，将几大模块组成一个协调完整 的能实现其功能的程序，最后提交设计报告二、系统分析:2.1设计思想用邻接矩阵来存储交通网络图的信息，运用迪杰斯特拉算法实现图上单源最 短路径问题，然后运用费洛伊德算法实现图中任意一对顶点间最短路径问题，这 样就会实现旅客所要咨询的问题。2.2设计要求该交通咨询系统要完成城市网络图的存储，并要实现求任意一个城市顶点到 其他城市顶点的最短路径问题，还要实现任意两个城市顶点间的 最短路径问 题。故设计要分成三部分，一是建立交通网络图的存储结构；二是解决单源路径 问题；最后再实现两个城市之间的最

5、短路径问题。设计要求：1. 建立交通网络网的存储结构。2. 总体设计要画流程图。3. 提供程序测试方案。4. 界面友好。2.3需求分析根据要求，需要在系统中建立无向图。系统应该有高度灵活性，可以由用 户根据当前交通网络图输入初始数据，并且可以更改。系统根据用户的输入建立 无向图的结构，并通过狄克斯特拉算法和弗洛伊德算法实现要求，并提供两种功 能供用户选择。2.4算法描述能狄克斯特拉算法的具体流程图i+in弗洛伊德算法的具体流程图三、概要设计:程序中将涉及下列两个抽象数据类型：一个是图，一个是队列。1、设定“图”的抽象数据类型定义：ADT Graph数据对象V： V是具有相同特性的数据元素的集合

6、，称为顶点集。数据关系R：R=VRVR = 1 v, w E VP(v, w), 表示从 v 到 w 的弧，谓词P(v, w)定义了弧的意义或信息基本操作P:CreateGraph(&GV,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图。LocateVex(Gu);初始条件：图G存在，u和G中的顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他 信息。First_next_adj (G， v) ；初始条件：图G存在，v是G中某个顶点。操作结果：返回V的第一个邻接顶点。若顶点在G中没有邻接顶点，则返 回“空”。DFSTrave

7、rse(Gi);初始条件：图G存在，i为某个顶点在邻接矩阵中的位置。操作结果：以i为起始点，对图进行深度优先遍历。BFSTraverse(Gi);初始条件：图G存在，i为某个顶点在邻接矩阵中的位置。操作结果：以i为起始点，对图进行广度优先遍历。 ADT Graph2、设定队列的抽象数据类型定义：ADT Queue数据对象：D= a i a i E BiTree, i E N+ 数据关系：R1=(| a i -1 , a i E D ,i=2,.，n约定a1端为队列头，a n端为队列尾。基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。EnQueue(&Q,&e)初始条件：队列Q已

8、存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q)初始条件：队列Q已存在。操作结果：删除Q的对头元素，并返回其值。QueueEmpty(&Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回1,否则0。QueueLenghth（Q）初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列长度。GetHead（Q，&e）初始条件：Q为非空队列。操作结果：用e返回Q的对头元素。 ADT Queue3、本程序包含三个模块1）主程序模块void main（）选择欲建图的类型；构建图并对其用邻接矩阵的形式打印；对图进行深度和广度优先搜索以及求某个顶点的第一邻接点;求某一源点到其

9、余顶点的最短路径。2）图模块实现图的抽象数据类型和基本操作3）队列模块实现队列的抽象数据类型及今本操作3.1程序流程图四、详细设计:4.1建立图的存储结构首先定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩 阵。设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下定义 的n阶方阵。JW，若（讨,vj）或 vi,vj e E（G）;Ar,门0或8,当不满足上述条件时。Ai，j= i当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接 矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信

10、息，其中下 标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下： #definf MVNum 88 最大顶点数 typedef struct（VertexType vexsMVNum;顶点数组，类型假定为char型Adjmatrix arcsMVNumMVNum;邻接矩阵，假定为 int 型MGraph;4.2单源最短路径最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带 权），我们希望找出从某个源点Se V到G中其余各顶点的最短路径。为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终 点。那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（D

11、ijkstra）提 出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。迪杰斯特拉算法求最短路径的实现思想是：设G=（V，E）是一个有向图，结点集为，V = v,v, .,v ，cost是表示G的邻接矩阵，costij表示有向 12n边i,j的权。若不存在有向边i,j，则costij的权为无穷大（这里取值 为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶 点的最短距离已经求出。设顶点v为源点，集合S的初态只包含一个元素，即 顶点v1。数组dist记录从源点到其他顶点当前的最短距离，其初值为 disti=costv1i,i=1,2,n。从S之外的顶点集合V-S

12、中选出一个顶点w，使distw的值最小。于是从源点到达w只通过S中顶点，把w加入集合S 中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的distv 和distw+costwv中选择较小的值作为新的distv。重复上述过程，直到 V-S为空。最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist 记录了源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组， 其中pathi表示从源点到顶点i之间的最短路径的前驱顶点。因此，迪杰斯特拉算法可用自然语言描述如下：初始化S和D，置空最短路径终点集，置初始的最短路径值;Sv1=TRUE; Dv1=0；/S集初始

13、时只有源点，源点到源点的距离为0；While （S集中顶点数n）（开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中；Sv=TRUE；1更新当前最短路径及距离；4.3任意一对顶点间最短路径任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V，E），要对 G中任意一对顶点有序对v,w（v w）”，找出v到w的最短路径。要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执 行前面讨论的迪杰斯特拉算法n次，即可以求得每对顶点之间的最短路径。这里还可以用另外一种方法，称作费洛伊德（Floyd）算法。费洛伊德（Floyd）算法算法的基本思想是：假设求从顶点v0vT最短路 径

14、。如果从v到v存在一条长度为arcsij的路径，该路径不一定是最短路 径，还需要affn次试探。首先考虑路径3广1 和v1,v是否存在。如果存在， 则比较v ,v 和 v ,v ,v 的路径长度，取长度较短者为当前所求得的最短路 径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从v到v是否包 含有顶点v为中间顶点的路径v,v,v，若没有，则说明从: v 到 v的当 22j.ij刖最短路径就是刖一步求出的；若有，那么v ,，v ,，v 可分解为v,v i2i2和v ,v ,而这两条路径是前一次找到的中间顶点序号不大于1的最短路径， 将这两条路径长度相加就得到路径v ,v ,v 的长度。将该

15、长度与前一次 中求出的从v到v的中间顶点序号不大于1的最短路径比较，取其长度较短者 作为当前求得的从jv到v的中间顶点序号不大于2的最短路径。依此类推，直 到顶点v加入当前从: v ajv的最短路径后，选出从v到v的中间顶点序号不大 于n的最短路径为止。由于图G中顶点序号不大于n，i所以jv到v的中间顶点序 号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就 是v.到v.的最短路径。4.4建立有向图的存储结构void CreateMGraph(MGraph * G, int n, int e)(int i,j,k,w;for(i=1;ivexsi = (char)i;for

16、(i=1;i=n;i+)for(j=1;jarcsij=Maxint;printf(输A%d条边的 i,j 及w:n，e);for(k=1;karcsij=w;printf(有向图建立完毕n)；4.5迪杰斯特拉算法void Dijkstra(MGraph *G, int v1, int n)(int D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v;if (D2vMaxint)P2v=v1;elseP2v=0;D2v1=0;Sv1=TRUE;for(i=2;in;i+)(min=Maxint;for(w=1;w

17、=n;w+)if(!Sw&D2wmin)(v=w;min=D2w;Sv=TRUE;for(w=1;warcsvwarcsvw;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)；4.6弗洛伊德算法void Floyd(MGraph *G, int n)(int i,j,k,v,w;for(i=1;i=n;i+)for(j=1;jarcsij!=Maxint)Pij=j;elsePij=0;Dij=G-arcsij;

18、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;4.7运行主控程序void main()(MGraph *G;int m,n,e,v,w,k;int xz=1;G=(MGraph *)malloc(sizeof(MGraph);printf(输入图中顶点个数和边数n,e:)； scanf(d,%d，&n,&e);CreateMGraph(G,n,e);while (xz!=0)(一printf(*求城市间的最短路径*n)； printf(1.求一个城市到所有城市的最短路径n)； p

19、rintf(2.求任意的两个城市之间的最短路径n)； printf(请选择：1或2,选择0退出：)； scanf(d,&xz);if (xz=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,v); while(k!=w)(printf(d，k);k=Pkw;printf（一d,w）;printf（路径长度:%dn”,Dvw）;else if（xz=1）（printf（求单源路径，输入源点v

20、 :）;scanf（d，&v）;Dijkstra（G,v,n）;printf（结束求最短路径）；五、运行与测试：1、进入查询系统并设置城市个数及城市间连接情况族迎使用交通查询系统PE俞入完文本后，均也EMw结束 俞入顶点和诃数时请使用*:号隔吏用查询功能前？请输入顶点奔数和边数育输入&条边的LL及y,5,12-,.4.15L3.1?5,18i. 1.13也图的结构建立成功I2、进入查询界面，按要求“ 1”进行查询3、在查询界面，按要求“2”进行查询 求城市之间的最短路径 +顼ilii噩i$li暨请选择：1或2 ,选择e退出：:青输X起点和终点.用盘L号隔开号U3区带罟茬盈蔚最短路隹岩12f5F

21、3 路径奖鱼时4、退出查询界面清选择：1或2 F选择谒退出程序已结束，谢谢您的使用！Press an梨 key to continue六、：总结与心得在第一次编译时出现了很多错误，是因为我对C语言的不熟练，比如调用 费洛伊德算法时出现了调用的错误，找了好久，才改正过来，还有就是for语句 的运用，由于本次程序要用很多for循环，我把一次for循环放到了上面for循环 中，导致程序不能正确输出结果。最后把调到外面才能运行。通过本实验基本掌握了这两个算法的应用，编程过程中有过很多失误，可知 对平时的学习还有很多不够仔细的地方，通过这次设计，我学到了很多。附录：程序代码#include#includ

22、e#define Num 288定义常量 Num#define Maxint 31111enum booleanFALSE,TRUE;定义布尔类型typedef char VertexType;typedef int Adjmatrix;typedef structVertexType vexsNum;顶点数组，类型假定为char型Adjmatrix arcsNumNum;MGraph;/邻接矩阵，假定为int型int D1Num,P1Num;int DNumNum,PNumNum;void CreateMGraph(MGraph *G,int n,int e); /采用邻接矩阵表示法构造有向

23、图G,n,e表示图的 当前顶点数和边数void Dijkstra(MGraph *G,int v1,int n);/狄克斯特拉算法的声明void Floyd(MGraph *G,int n);弗洛伊德算法的声明void main() MGraph *G;system(color 1f);定义无向图 Gint n,e,v,w,k;int m=1;G=(MGraph *)malloc(sizeof(MGraph);printf(*n);printf(*欢迎使用交通查询系统*n);printf(”*=*n”);printf(* ?$:输入完文本后，均以Enter结束!*n);printf(*输入顶点

24、和边数时请使用“,”号隔*n);printf(* 开*n);printf(*n);printf(n);printf(使用查询功能前，请输入顶点个数和边数n,e：);scanf(%d,%d”,&n,&e);CreateMGraph(Gn,e);调用CreateMGraph有向图函数while(m!=0)printf(”= =n);printf( A_A 求城市之间的最短路径 A_A n);printf(”=n”)；printf(1 :求一个城市到其他所有城市的最短路径);printf(2 :求任意的两个城市之间的最短路径n);printf(”=n”)；printf( 请选择：1或2，选择0退出：

25、n);scanf(%d”,&m);if(m=2)Floyd(G,n);printf(-请输入起点和终点，用“,”号隔开：n);scanf(%d,%d”,&v,&w);k=Pvw;if(k=0)printf(n输出的结果：n顶点d到d无路径!n”,v,w);elseprintf(n输出的结果：n从顶点d到d的最短路径是:d”,v,w,v);while(k!=w)printf(%d”,k);k=Pkw;printf(%d”,w);printf(n路径长度:%dn,Dvw);elseif(m=1)printf(请输入起点编号：n);scanf(%d”,&v);Dijkstra(Gv,n);print

26、f(程序已结束!谢谢您的使用!n);void CreateMGraph(MGraph *Gint n,int e)构建城市的无向图int i,j,k,w;for(i=1;ivexsi=(char)i;for(i=1;i=n;i+)for(j=1;jarcsij=Maxint;/距离初始化if(i=j)G-arcsij=0;printf(n 请输A%d 条边的 i,j,及 w： n,e);for(k=1;karcsij=w;建立城市之间的距离printf(n地图的结构建立成功!n);/狄克斯特拉算法求一个城市到任意一个城市的void Dijkstra(MGraph *G,int v1,int n

27、) 距离int D2Num,P2Num;int v,i,w,min;enum boolean SNum;for (v=1;varcsv1v;if(D2varcsvwD2w) /修改不在 s 中的顶点的距离P2v1=0;Sv1=TRUE;for(i=2;in;i+)min=Maxint;for(w=1;w=n;w+)if(!Sw&D2wmin)v=w;min=D2w; Sv=TRUE;for(w=1;warcsvw;P2w=v;输出最短路径printf(n 输出的结果：n);printf(路径长度路径);for(i=1;i=n;i+)printf(%5d”,D2i);printf(%10d”,i

28、); v=P2i; while(v!=0)printf(”J%d”,v);v=P2v;printf(n);void Floyd(MGraph *G,int n)/用弗洛伊德算法求任意两顶点最短距离定义三个变量int i,j,k;for(i=1;i=n;i+)for(j=1;jarcsij!=Maxint)Pij=j;elsePij=0;Dij=G-arcsij;以k为源点循环求出所有顶点的最短路径for(k=1;k=n;k+) for(i=1;i=n;i+)/i为已知最短路径的顶点for(j=1;j=n;j+)/j为未知最短路径的顶点 if(Dik+DkjDij)(Dij=Dik+Dkj;Pij=Pik;