交通咨询系统设计

1目录1概述..............................................................................................................................................21.1问题描述............................................................................................................................21.2实现意义............................................................................................................................22系统分析......................................................................................................................................22.1需求分析............................................................................................................................22.1.1程序的功能..............................................................................................................22.1.2输入输出的要求......................................................................................................22.2设计思想............................................................................................................................22.3设计要求............................................................................................................................33概要设计......................................................................................................................................33.1建立图的存储结构.............................................................................................................33.2单源最短路径....................................................................................................................33.3任意一对顶点间最短路径................................................................................................44详细设计......................................................................................................................................44.1用邻接矩阵构造图结构函数CreateMGraph()................................................................44.2费洛伊德Floyd()...............................................................................................................54.3迪杰斯特拉Dijkstra().......................................................................................................54.4主要函数流程图及其函数调用........................................................................................64.4.1主要函数流程图.....................................................................................................64.4.2一个城市到其他城市的路径调用.........................................................................74.4.3任意两个城市之间路径调用.................................................................................75运行与测试..................................................................................................................................75.1有向图存储结构的建立模块的输出................................................................................85.2单源路径迪杰斯特拉算法模块的输出............................................................................95.3费洛伊德算法模块的输出................................................................................................96总结与心得..................................................................................................................................9参考文献........................................................................................................................................10附录................................................................................................................................................1021概述1.1问题描述在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出差、旅游或做其它出行时，不仅关心节省费用，而且对里程和所需时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城市之间的交通关系。这个交通系统可以回答旅客提出的各种问题。比如任意一个城市到其他城市的最短路径，任意两个城市之间的最短路径问题。1.2实现意义便于人们的日常出行，且更好地满足了用户的出行需求。这种最短路径问题的计算方法既简单又便于实现，同时大大提高了计算机的运行速率。2系统分析2.1需求分析2.1.1程序的功能（1）用户自己可以建立不同的路径之间的关系网（2）可以查询某个城市到达其余各城市的最短路径。（3）可以任一查询两个城市之间的最短路径。2.1.2输入输出的要求在刚进入主界面后系统提示输入建立交通网络储存结构，输入顶点个数和和边数为整数不能输入其他字符，随后系统提示输入边与边之间的关系分别为i，j，w表示边之间的距离。然后进入查询页面，输入整数1，2，0分别表示你所要查询的功能：一个城市至其他所有城市的最短路径查询、任意两个城市之间的最短路径查询、退出程序。不能输入其他字符否则不能执行操作。在整个操作都是用整数表示城市。2.2设计思想用邻接矩阵来存储交通网络图的信息，运用迪杰斯特拉算法实现图上单源最短路径问题，然后运用费洛伊德算法实现图中任意一对顶点间最短路径问题，这样就会实现交通咨询系统设计的问题。32.3设计要求该交通咨询系统要完成城市网络图的存储，并要实现求任意一个城市顶点到其他城市顶点的最短路径问题，还要实现任意两个城市顶点间的最短路径问题。故设计要分成三部分，一是建立交通网络图的存储结构；二是解决单源路径问题；最后再实现两个城市之间的最短路径问题。3概要设计3.1建立图的存储结构首先要定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=（V,E）是具有n个顶点的图，则G的邻接矩阵是具有如下定义n阶方阵。A[i,j]=Wi,j若（vi，vj）或vi,vj€E(G);0或∞，当不满足上述条件时。一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下表为i的元素存储顶点v的信息。因此，图的邻接矩阵的存储结构定义如下：#defineMVNum50//最大顶点数typedefstruct{VertexTypevexs[MvNum];Adjmatrixarcs[MVNum][MVNum];}MGraph;3.2单源最短路径单源路径问题：即已知有向图（带权），我们希望找出从某个源点S€V到G中其余各顶点的最短路径。为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点称为终点。迪杰斯特拉算法求最短路径的实现思想：设有向图G=（V,E），其中，V={1,2,…,n},cost是表示G的邻接矩阵，cost[i][j]表示有向边i,j的权。若不存在有向边i,j，则cost[i][j]的权为无穷大（这里取值为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已近求出。设顶点v1为源点，集合S的初态只包含顶点v1。数组dist记录从源点到其他各顶点当前的最短距离，其初值为dist[i]=cost[v1][i],i=1,2,...,n。从S之处的顶点集合V-S中选出一个顶点w，使dist[w]的值最小。于是从源点到达w只通过s中的顶点，把w加入集合S中，调整dist中记录的源点到V-S中每个顶点v的距离：从原来的di