最短路径设计报告(秦浩).doc

青岛理工大学琴岛学院设 计 报 告课题名称：求解最优交通路径学 院：青岛理工大学琴岛学院专业班级：计算机网络技术1班学 号：20120361105学 生：秦浩指导教师：薛晓亚青岛理工大学琴岛学院教务处2013年 07 月 02 日学 生秦浩 指导教师 薛晓亚课题名称求解最优交通路径设计时间2013/07/012013/07/05设计地点8-205、8-212设计目的1.熟悉用vc编写应用程序的基本方法。2.理解掌握地杰斯特拉算法或弗洛伊德算法的思想。3强化最优路径算法在实际中的应用。指导教师评语系部教研室意 见一、需求分析1.选题：俗话说，条条大路通罗马，世界上从一个地方去另一个地方的路有很多，而且有长有远，所以，平时人们在出行时靠人脑来计算路的长短很不方便，我们就这个问题设计了这个程序。本程序实现迪杰斯特拉算法。图存储采用了邻接矩阵存储结构。对于带有权值的网络图求解最小路径问题，一般有两种算法：迪杰斯特拉和弗洛伊德算法，前者是求解单源最短路径问题，后者是求全源最短路径问题。就本程序而言用迪杰斯特拉比较简单，因而采用前者。2功能划分： 本程序可以查询给出城市中任意两个城市的最短路径，将各城市的名称输出和两个城市之间的距离输出，管理员可以修改两个城市之间的距离，并且可以任意删除插入任意一条路径，重新输出两个城市的距离。用户输入起点和终点后查找所有的路线，并计算距离找出最短路线；显示所走路线经过的站名和单程路线所经过的距离，并显示所要经过的站点数量；路线用图示的方法显示；输入目的地查询是否存在，如果存在就提供路线，如果没有则提示退出。二、详细设计(具体表述你的设计是如何一步步实现的)1. 图的存储首先创建CreatUDN( )函数生成一个拥有25个城市，30条公路的交通图，并录入两城市之间的权值即距离，其中顶点对应于城市，边对应于城市间直接通路，根据实际问题，在生成的交通图中所有的通路都是双向的，即如果A城市到B城市有直接通路，且里程为k千米，则B城市到A城市也有直接通路，并且里程同样为k千米。邻接矩阵的实现：定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。Ai，j= 当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下：typedef structVertexType vex25; /*图中的顶点，即为城市*/ArcCell arcs2525; /*图中的边，即为城市间的距离*/int vexnum,arcnum; /*顶点数，边数*/MGraph; /*定义图的类型*/ 2、界面设计（1）通过CreatUDN( )函数生成一个拥有25个城市，30条公路的交通图;调用narrate( )函数输出提示信息，提示用户输入发出城市和终到城市的序号，narrate( )函数把能够进行计算的城市列表按简单的格式进行输出。（2）由Output( )函数输出结果;最终退出main结束main( )函数，退出程序。2.重要函数设计 在函数设计上面，首先要先将图录入存储到整个算法中，然后通过函数的调用，来为用户提供服务。在这个过程中，1、 CreateUND( )函数根据用户输入的顶点数和边数生成一个相应的交通图，其中顶点对应于城市，边对应于城市间直接通路。2、 运用narrate函数来对用户加以引导。3、然后运用函数ShortestPath来根据用户的要求指令来求出用户所需要的最短路径。为了便于ShortestPath( )函数的计算，在生成的交通图中所有的通路都是双向的，即如果A城市到B城市有直接通路，且里程为k千米，则B城市到A城市也有直接通路，并且里程同样为k千米。4、用输出函数output输出运算完成的结果呈现在用户操作界面。5、最后运用一个主要函数main来将各个函数进行串联。 其中： P表示两个顶点之间的最短路径 D表示带权路径长度 。D(v)为v0到v的路径长度。进入查询界面是否继续查询选择查看各城市对应的编号判断前后两次输入的编号是否在查询范围之内输入要查询的两个城市编号输出两站点路径及最短距离退出否是YN p(v)记录v0到v的最短路径，若pvw为TRUE，则w是从v0到v当前求得最短路径上的顶点。开始CreatUDN()创建界面ShortestPath( )计算出最短路径及距离Output()输出起点和终点以及中间的点输出最短路径及距离结束输入要查询的两个城市编号 图 1（此为程序主流程图） 图2（此为查询流程图）三、遇到问题和解决方法：问题1：在执行程序的时候不能显示最短的距离。解决方法：增加一个函数调用，调用的函数为ShortestPath(v0); /*计算两个城市之间的最短路径*/ 问题2：不能连续查询，即查询一次完成后，必须重新运行才能就进行二次查询。 解决方法：在代码中添加while( ) 语句 printf(是否继续，1（继续查询），0（退出查询）);printf(n); scanf(%d,&ch); 4、 总结与展望： 在课程设计的过程中，反映出了我们平时学习不扎实的现象，有时对于课本上所说的知识一头雾水。用C语言编程序时错误百出，这也表现出我们对实际操作的生疏，上机写程序时把程序语言的字母打错，前后设置的变量结合不起来等，反映了我们平时真的需要多实践，多去自己钻研一些问题。最短路径算法关键先把已知最短路径顶点集(只有一个源点)和未知的顶点分开，然后依次把未知集合的顶点按照最短路径(这里特别强调一下是源点到该顶点的路径权重和，不仅仅是指它和父结点之间的权重，一开始就是在没有这个问题弄清楚)加入到已知结点集中。在加入时可以记录每个顶点的最短路径，也可以在加入完毕后回溯找到每个顶点的最短路径和权重。在本次课程设计中我也了解了网上的一些查找最短路线软件的工作原理，感觉学到的东西能够与实际生活结合起来，这让我看到了学习课本知识的