最短路径的设计汇报[秦浩].docVIP

PAGE  PAGE 6 青岛理工大学琴岛学院 设 计 报 告 课题名称：求解最优交通路径 学 院：青岛理工大学琴岛学院 专业班级：计算机网络技术1班 学 号：20120361105 学 生：秦浩 指导教师：薛晓亚 青岛理工大学琴岛学院教务处 2013年 07 月 02 日 学 生秦浩 指导教师 薛晓亚课题名称求解最优交通路径设计时间2013/07/01~2013/07/05设计地点8-205、8-212设计目的1.熟悉用vc编写应用程序的基本方法。 2.理解掌握地杰斯特拉算法或弗洛伊德算法的思想。 3．强化最优路径算法在实际中的应用。指导教师评语 系部教研室 意 见  一、需求分析 1.选题： 俗话说，条条大路通罗马，世界上从一个地方去另一个地方的路有很多，而且有长有远，所以，平时人们在出行时靠人脑来计算路的长短很不方便，我们就这个问题设计了这个程序。本程序实现迪杰斯特拉算法。图存储采用了邻接矩阵存储结构。对于带有权值的网络图求解最小路径问题，一般有两种算法：迪杰斯特拉和弗洛伊德算法，前者是求解单源最短路径问题，后者是求全源最短路径问题。就本程序而言用迪杰斯特拉比较简单，因而采用前者。 2功能划分： 本程序可以查询给出城市中任意两个城市的最短路径，将各城市的名称输出和两个城市之间的距离输出，管理员可以修改两个城市之间的距离，并且可以任意删除插入任意一条路径，重新输出两个城市的距离。用户输入起点和终点后查找所有的路线，并计算距离找出最短路线；显示所走路线经过的站名和单程路线所经过的距离，并显示所要经过的站点数量；路线用图示的方法显示；输入目的地查询是否存在，如果存在就提供路线，如果没有则提示退出。 二、详细设计 (具体表述你的设计是如何一步步实现的) 图的存储 首先创建CreatUDN( )函数生成一个拥有25个城市，30条公路的交通图，并录入两城市之间的权值即距离，其中顶点对应于城市，边对应于城市间直接通路，根据实际问题，在生成的交通图中所有的通路都是双向的，即如果A城市到B城市有直接通路，且里程为k千米，则B城市到A城市也有直接通路，并且里程同样为k千米。 邻接矩阵的实现： 定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。 A[i，j]= 当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。 图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下： typedef struct{ VertexType vex[25]; /*图中的顶点，即为城市*/ ArcCell arcs[25][25]; /*图中的边，即为城市间的距离*/ int vexnum,arcnum; /*顶点数，边数*/ }MGraph; /*定义图的类型*/ 2、界面设计 （1）通过CreatUDN( )函数生成一个拥有25个城市，30条公路的交通图;调用narrate( )函数输出提示信息，提示用户输入发出城市和终到城市的序号，narrate( )函数把能够进行计算的城市列表按简单的格式进行输出。 （2）由Output( )函数输出结果;最终退出main结束main( )函数，退出程序。 2.重要函数设计 在函数设计上面，首先要先将图录入存储到整个算法中，然后通过函数的调用，来为用户提供服务。在这个过程中， CreateUND( )函数根据用户输入的顶点数和边数生成一个相应的交通图，其中顶点对应于城市，边对应于城市间直接通路。 运用narrate函数来对用户加以引导。 3、然后运用函数ShortestPath来根据用户的要求指令来求出用户所需要的最短路径。为了便于ShortestPath( )函数的计算，在生成的交通图中所有的通路都是双向的，即如果A城市到B城市有直接通路，且里程为k千米，则B城市到A城市也有直接通路，并且里程同样为k千米。 4、用输出函数output输出运算完成的结果呈现在用户操作界面。 5、最后运用一个主要函数main来将各个函数进行串联。 其中： P表示两个顶点之间的最短路径 D表示带权路径长度 。 D(v)为v0到v的路径长度。 进入查询界面 是否继续查询选择 查看各城市对应的编号 判断前后两次输入的编号是否在查询范围之内 输入要查询的两个城市编号 输出两站点路径及最短距离 退出 否 是 Y N p(v)记录v0到v的最短路径，若p[v][w]为TRU