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

《数据结构实验报告五最短路径.doc》由会员分享，可在线阅读，更多相关《数据结构实验报告五最短路径.doc（19页珍藏版）》请在三一文库上搜索。

1、实验课程名称 数据结构课程设计 专 业 班 级 学 生 姓 名 学 号 指 导 教 师 2012至 2013学年第 一 学期第 1 至 9 周目录一、概述：21.1 问题描述21.2 系统实现的目标21.3 系统实现方案2二、系统分析：32.1设计思想32.2设计要求32.3需求分析32.4 算法描述4三、概要设计：63.1 程序流程图7四、详细设计：84.1建立图的存储结构84.2单源最短路径84.3任意一对顶点间最短路径94.4 建立有向图的存储结构104.5迪杰斯特拉算法104.6弗洛伊德算法114.7 运行主控程序12五、运行与测试：13六、：总结与心得15附录：程序代码15一、概述：

2、1.1 问题描述在交通网络非常发达,交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从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=1j=1;j+;jn弗洛伊德算法的具体

6、流程图开 始初始化距离和路径设为从到的只以集合中的节点为中间节点的最短路径的长度输出结果最短路径经过点k最短路径不经过点k三、概要设计：程序中将涉及下列两个抽象数据类型：一个是图，一个是队列。 1、设定“图”的抽象数据类型定义： ADT Graph 数据对象 V：V 是具有相同特性的数据元素的集合,称为顶点集。 数据关系 R： R=VRVR = | v, w VP(v, w), 表示从v到w的弧， 谓词P(v, w)定义了弧 的意义或信息基本操作 P：CreateGraph(&G,V,VR); 初始条件：V 是图的顶点集，VR 是图中弧的集合。 操作结果：按 V 和 VR 的定义构造图。 Lo

7、cateVex(G,u); 初始条件：图 G 存在，u 和 G 中的顶点有相同特征。 操作结果：若 G 中存在顶点 u，则返回该顶点在图中位置；否则返回其他信息。 First_next_adj（G，v） ； 初始条件：图 G 存在，v 是 G 中某个顶点。 操作结果：返回 V 的第一个邻接顶点。若顶点在 G 中没有邻接顶点，则返回“空” 。 DFSTraverse(G,i); 初始条件：图 G 存在，i 为某个顶点在邻接矩阵中的位置。 操作结果：以 i 为起始点，对图进行深度优先遍历。 BFSTraverse(G,i); 初始条件：图 G 存在，i 为某个顶点在邻接矩阵中的位置。 操作结果：以

8、 i 为起始点，对图进行广度优先遍历。 ADT Graph 2、设定队列的抽象数据类型定义： ADT Queue 数据对象：D= a i a i BiTree, i N+ 数据关系：R1=| a i 1 , a i D ,i=2,，n 约定 a1 端为队列头， a n 端为队列尾。基本操作： InitQueue(&Q) 操作结果：构造一个空队列 Q。EnQueue(&Q,&e) 初始条件：队列 Q 已存在。 操作结果：插入元素 e 为 Q 的新的队尾元素。 DeQueue(&Q) 初始条件：队列 Q 已存在。 操作结果：删除 Q 的对头元素，并返回其值。 QueueEmpty(&Q) 初始条件

9、：队列 Q 已存在。操作结果：若 Q 为空队列，则返回 1，否则 0。 QueueLenghth(Q) 初始条件：队列 Q 已存在。 操作结果：返回 Q 的元素个数，即队列长度。 GetHead（Q，&e） 初始条件：Q 为非空队列。 操作结果：用 e 返回 Q 的对头元素。 ADT Queue 3、本程序包含三个模块1）主程序模块 void main( ) 选择欲建图的类型； 构建图并对其用邻接矩阵的形式打印； 对图进行深度和广度优先搜索以及求某个顶点的第一邻接点； 求某一源点到其余顶点的最短路径。 2）图模块实现图的抽象数据类型和基本操作 3）队列模块实现队列的抽象数据类型及今本操作3.1

10、 程序流程图四、详细设计：4.1建立图的存储结构首先定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。Ai，j= 当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下：#definf MVNum 88 /最大顶点数typedef struct VertexType vexsMVNum; /

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

12、边的权。若不存在有向边，则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为空。最终结果是

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

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

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

16、建立有向图的存储结构void CreateMGraph(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=Maxint; printf(输入%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;

17、varcsv1v; if(D2vMaxint) P2v=v1; else P2v=0; D2v1=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;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

18、 Floyd(MGraph *G,int n) int i,j,k,v,w; for(i=1;i=n;i+) for(j=1;jarcsij!=Maxint) Pij=j; else Pij=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; 4.7 运行主控程序void main()MGraph *G; int m,n,e,v,w,k; int xz=1; G=(MGraph *)malloc(sizeof(MGraph); printf(输

19、入图中顶点个数和边数n,e:); scanf(%d,%d,&n,&e); CreateMGraph(G,n,e); while (xz!=0) printf(*求城市间的最短路径*n); printf(1.求一个城市到所有城市的最短路径n); printf(“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

20、); 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 :); scanf(%d,&v); Dijkstra(G,v,n); printf(结束求最短路径);五、运行与测试：1、进入查询系统并设置城市个数及城市间连接情况2、进入查询界面，按要求“1”进行查询3、在查询界面，按要求“2”进行查询4、退出查询界面六、：总结与心得在第一次编译时出现了很多错误，是因为我对C

21、语言的不熟练，比如调用费洛伊德算法时出现了调用的错误，找了好久，才改正过来，还有就是for语句的运用，由于本次程序要用很多for循环，我把一次for循环放到了上面for循环中，导致程序不能正确输出结果。最后把调到外面才能运行。通过本实验基本掌握了这两个算法的应用，编程过程中有过很多失误，可知对平时的学习还有很多不够仔细的地方，通过这次设计，我学到了很多。 附录：程序代码#include#include#define Num 288 /定义常量Num#define Maxint 31111enum booleanFALSE,TRUE; /定义布尔类型typedef char VertexType

22、;typedef int Adjmatrix;typedef struct VertexType vexsNum; /顶点数组， 类型假定为char型 Adjmatrix arcsNumNum;MGraph; / 邻接矩阵， 假定为int型int D1Num,P1Num;int DNumNum,PNumNum;void CreateMGraph(MGraph *G,int n,int e); /采用邻接矩阵表示法构造有向图G,n,e表示图的当前顶点数和边数void Dijkstra(MGraph *G,int v1,int n); /狄克斯特拉算法的声明void Floyd(MGraph *G

23、,int n); /弗洛伊德算法的声明void main() MGraph *G; system(color 1f); /定义无向图G int n,e,v,w,k; int m=1; G=(MGraph *)malloc(sizeof(MGraph); printf(*n); printf(* 欢迎使用交通查询系统 *n); printf(*=*n); printf(* PS:输入完文本后，均以Enter结束!*n); printf(*输入顶点和边数时请使用“,”号隔 *n); printf(*开! *n); printf(*n); printf(n); printf(使用查询功能前，请输入顶

24、点个数和边数n,e：); scanf(%d,%d,&n,&e); CreateMGraph(G,n,e); /调用CreateMGraph有向图函数 while(m!=0) printf(=n); printf( _ 求城市之间的最短路径 _ n); printf(=n); printf(1 : 求一个城市到其他所有城市的最短路径n); printf(2 : 求任意的两个城市之间的最短路径n); printf(=n); printf( 请选择：1 或 2 ，选择 0 退出：n); scanf(%d,&m); if(m=2) Floyd(G,n); printf(请输入起点和终点，用“,”号隔开

25、：n); scanf(%d,%d,&v,&w); k=Pvw; if(k=0) printf(n输出的结果：n顶点%d到%d无路径!n,v,w); else printf(n输出的结果：n从顶点%d到%d的最短路径是: %d,v,w,v); while(k!=w) printf(%d,k); k=Pkw; printf(%d,w); printf(n 路径长度: %dn,Dvw); else if(m=1) printf(请输入起点编号：n); scanf(%d,&v); Dijkstra(G,v,n); printf(程序已结束!谢谢您的使用!n);void CreateMGraph(MGr

26、aph *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=Maxint; /距离初始化 if(i=j) G-arcsij=0; printf(n请输入%d条边的i,j,及w： n,e); for(k=1;karcsij=w; /建立城市之间的距离 printf(n地图的结构建立成功！n);void Dijkstra(MGraph *G,int v1,int n) /狄克斯特拉算法求一个城市到任意一个城市的距离 int D2Num,P2Num; int v,

27、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;warcsvwarcsvw; P2w=v; printf(n输出的结果：n); print

28、f(路径长度 路径n); /输出最短路径 for(i=1;i=n;i+) printf(%5d,D2i); printf(%10d,i); v=P2i; while(v!=0) printf(%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;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;