最短路径设计报告秦浩

《最短路径设计报告秦浩》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、青岛理工大学琴岛学院设计报告课题名称：求解最优交通路径学院：青岛理工大学琴岛学院专业班级：计算机网络技术1班学号：20120361105学生：秦浩指导教师：薛晓亚青岛理工大学琴岛学院教务处2013年07月02日6学生秦浩指导教师薛晓亚课题名称求解最优交通路径设计时间2013/07/01~2013/07/05设计地点8-205、8-212设计目的1.熟悉用vc编写应用程序的基本方法。2.理解掌握地杰斯特拉算法或弗洛伊德算法的思想。3．强化最优路径算法在实际中的应用。指导教师评语系部教研室意见6一、需求分

2、析1.选题：俗话说，条条大路通罗马，世界上从一个地方去另一个地方的路有很多，而且有长有远，所以，平时人们在出行时靠人脑来计算路的长短很不方便，我们就这个问题设计了这个程序。本程序实现迪杰斯特拉算法。图存储采用了邻接矩阵存储结构。对于带有权值的网络图求解最小路径问题，一般有两种算法：迪杰斯特拉和弗洛伊德算法，前者是求解单源最短路径问题，后者是求全源最短路径问题。就本程序而言用迪杰斯特拉比较简单，因而采用前者。2功能划分：本程序可以查询给出城市中任意两个城市的最短路径，将各城市的名称输出和两个城市之间的距

3、离输出，管理员可以修改两个城市之间的距离，并且可以任意删除插入任意一条路径，重新输出两个城市的距离。用户输入起点和终点后查找所有的路线，并计算距离找出最短路线；显示所走路线经过的站名和单程路线所经过的距离，并显示所要经过的站点数量；路线用图示的方法显示；输入目的地查询是否存在，如果存在就提供路线，如果没有则提示退出。二、详细设计(具体表述你的设计是如何一步步实现的)1.图的存储首先创建CreatUDN()函数生成一个拥有25个城市，30条公路的交通图，并录入两城市之间的权值即距离，其中顶点对应于城市，

4、边对应于城市间直接通路，根据实际问题，在生成的交通图中所有的通路都是双向的，即如果A城市到B城市有直接通路，且里程为k千米，则B城市到A城市也有直接通路，并且里程同样为k千米。邻接矩阵的实现：定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。A[i，j]=当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一

5、个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下：typedefstruct{VertexTypevex[25];/*图中的顶点，即为城市*/ArcCellarcs[25][25];/*图中的边，即为城市间的距离*/intvexnum,arcnum;/*顶点数，边数*/}MGraph;/*定义图的类型*/2、界面设计6（1）通过CreatUDN()函数生成一个拥有25个城市，30条公路的交通图;调用narrate()函数输出提示信息，提示

6、用户输入发出城市和终到城市的序号，narrate()函数把能够进行计算的城市列表按简单的格式进行输出。（2）由Output()函数输出结果;最终退出main结束main()函数，退出程序。62.重要函数设计在函数设计上面，首先要先将图录入存储到整个算法中，然后通过函数的调用，来为用户提供服务。在这个过程中，1、CreateUND()函数根据用户输入的顶点数和边数生成一个相应的交通图，其中顶点对应于城市，边对应于城市间直接通路。2、运用narrate函数来对用户加以引导。3、然后运用函数Shortest

7、Path来根据用户的要求指令来求出用户所需要的最短路径。为了便于ShortestPath()函数的计算，在生成的交通图中所有的通路都是双向的，即如果A城市到B城市有直接通路，且里程为k千米，则B城市到A城市也有直接通路，并且里程同样为k千米。4、用输出函数output输出运算完成的结果呈现在用户操作界面。5、最后运用一个主要函数main来将各个函数进行串联。其中：P表示两个顶点之间的最短路径D表示带权路径长度。D(v)为v0到v的路径长度。进入查询界面是否继续查询选择查看各城市对应的编号判断前后两次输

8、入的编号是否在查询范围之内输入要查询的两个城市编号输出两站点路径及最短距离退出否是YNp(v)记录v0到v的最短路径，若p[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点。开始CreatUDN()创建界面ShortestPath()计算出最短路径及距离Output()输出起点和终点以及中间的点输出最短路径及距离结束输入要查询的两个城市编号图1（此为程序主流程图）图2（此为查询流程图）三、遇到问题和解决方法：问题1：在执行程序的时候不能显示