交通咨询系统设计.doc

目录1 概述11.1 课程设计名称11.2 课程设计目的12 系统分析22.1 问题描述22.2 设计要求22.3 课程设计内容23 概要设计23.1 定义相关的数据类型23.2 总体结构图2图5.133.3 模块调用图3图5.234 详细设计34.1建立一个有向图的存储结构34.2 迪杰斯特拉算法34.3 费洛伊德算法34.4 主函数流程图45运行与测试6实例的运行数据6图5.465.1 有向图的存储结构建立65.2 单源最短路径75.3 任意一对顶点间最短路径76 总结与心得87 参考文献88 附录（程序源代码）81 概述1.1 课程设计名称交通咨询系统设计（最短路径问题）1.2 课程设计目的 充分了解并掌握最短路径问题及其应用，根据有向图的存储结构解决实际问题。 2 系统分析2.1 问题描述 对于该设计，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答2.2 设计要求1、 建立交通网络的存储结构2、 提供一个城市到任意城市最短路径查询功能3、提供任意两个城市间最短路径查询功能 4、提供程序测试算法5、界面友好 2.3 课程设计内容 设计一个交通咨询系统,能让旅客咨询从任一个城市定点到另一个城市定点之间的最短路径或最低花费或最少时间等问题。对于不同的咨询要求、可输入城市间的路程或所需时间或所需花费。3 概要设计3.1 定义相关的数据类型采用邻接矩阵定义图：typedef struct VertexType vexsMVNum;/顶点数组类型假定为char型 Adjmatrix arcsMVNumMVNum;/邻接矩阵假定为int型 MGraph; 建立图的存储结构 #include #include #define MVNum 100/最大顶点数 #define Maxint 32767 enum booleanFALSE,TRUE; typedef char VertexType; typedef int Adjmatrix; typedef struct VertexType vexsMVNum;/顶点数组类型假定为char型 Adjmatrix arcsMVNumMVNum;/邻接矩阵假定为int型 MGraph; /MGraph是以邻接矩阵存储的图类型 3.2 总体结构图 交通咨询管理系统单源路径查询问题建立有向图的存储结构任意一对顶点间最短路径 图5.13.3 模块调用图调用迪杰斯特算法void dijkstra主函数main调用费洛伊德算法void Floyd打印系统菜单创建有向图 void MGraph 图5.24 详细设计4.1建立一个有向图的存储结构 有向图的邻接矩阵是不对称的，实现其算法，我们只需要输入有向图的有向边及权值即可。采用邻接矩阵表示法构造有向图G，输入图中顶点个数和边数，初始化邻接矩阵，紧跟着系统提示输入边及权值，则系统提示有向图的存储结构建立完毕。4.2 迪杰斯特拉算法 为了解决单源路径问题，我们提出了迪杰斯特拉算法，它主要是按路径长度递增产生顶点的 最短路径算法，其实现如下： 初始化S和D，置空最短路径终点集，置初始的最短路径值； Sv1=TRUE;Dv1=0;/S集初始时只有源点，源点到源点的距离为0； While(S集中顶点数n) 开始循环，每次求得v1到某个v顶点的最短路径，并加V到S集中； Sv=TRUE; 更新当前最短路径及距离； 4.3 费洛伊德算法 任意一对顶点间最短路径，假设求从顶点vi到vj的最短路径。如果从vi到vj存在一条长度为arcsij的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径vi，v1和v1，vj是否存在。如果存在，则比较路径vi，vj和vi，v1，vj的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径vi，v2，vj，若没有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么vi，v2，vj可分解为vi，v2和v2，vj，而这两条路径是前一次找到的中间点序号不大于1的最短路径，将这两条路径长度相加就得到路径vi，v2，vj的长度。将该长度与前一次中求出的从vi到vj的中间顶点序号不大于2的最短路径。依次类推，直至顶点vn加入当前从vi到vj的最短路径后，选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到vj的最短路径。4.4 主函数流程图 开始建立图的存储结构 输入任一个城市顶点功能选择 0 2 1调用费洛伊德算法调用迪杰斯特算法 运行 输出结果 退出 结束 图5.3 5运行与测试实例的运行数据badcegf 图5.4 5.1 有向图的存储结构建立5.2 单源最短路径5.3 任意一对顶点间最短路径顶点4到7无路径：5.4 退出系统6 总结与心得 在本次实验过程中，输入错误还是存在的问题，书上代码还是有错误的，但能很快的通过编译解决，一些编译不能发现的问题，我们在组建过程中也能发现并解决。在组建过程中，总是显示连接错误，经过检查，程序代码没有错误。初步以为是系统在建立文件时的错误，经过从新建立一次文件，此错误解除了，原来是因为有其他程序在执行。 在该程序中，有向图的邻接矩阵是不对称的，实现其算法，我们只需要输入有向图的有向边及权值即可。 总的来说，这次课程设计还是学到了一些东西，经过我们不断的实验，找到了错误答案，学到了很多东西，所以在编程中和调试中要养成认真分析的善于发现问题并及时解决的习惯，不懂的及时问老师或其他同学。通过本次实验，让我们对图的基本结构有了更好的认识，有效的解决了最短路径问题，对两个算法的使用有了更好的掌握。7 参考文献1）徐孝凯，魏荣数据结构，机械工程出版社2) 谭浩强程序设计，北京大学出版社 3) 杨路明C语言程序设计教程，北京邮电大学出版社.4) 耿国华数据结构-C语言描述，高等教育出版社8 附录（程序源代码）#include#include#define MVNum 100 /最大顶点数#define Maxint 32767enum boolean FALSE,TRUE ;typedef char VertexType;typedef int Adjmatrix;typedef struct VertexType vexsMVNum; /顶点数组，类型假定为char型Adjmatrix arcsMVNumMVNum; /邻接矩阵，假定为int型MGraph;int D1MVNum,P1MVNum;int DMVNumMVNum,PMVNumMVNum;void CreateMGraph(MGraph *G,int n,int e) /采用邻接矩阵表示法构造有向图G，n,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);void Dijkstra(MGraph *G,int v1,int n) /用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径Pv及其权Dv /设G是有向图的邻接矩阵，若边不存在，则Gij=Maxint /Sv为真当且仅当v属于s,即已求得从v1到v得最短路径int D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v; /置初始的最短路径值if(D2vMaxint)P2v=v1; /v1是v的前驱（双亲）elseP2v=0; /v无前驱 /end forD2v1=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);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-arc