课程设计 单源点最短路径算法的实现

《课程设计 单源点最短路径算法的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计设计说明书单源点最短路径算法的实现学生姓名学号班级成绩指导教师数学与计算机科学学院2015年1月2日数据结构课程设计评阅书题目单源点最短路径算法的实现学生姓名学号指导教师评语及成绩成绩：教师签名：年月日教研室意见总成绩：室主任签名：年月日课程设计任务书2014—2015学年第1学期专业：学号：姓名：课程设计名称：数据结构课程设计设计题目：单源点最短路径算法的实现完成期限：自2014年12月22日至2015年1月2日共2周设计内容及要求:最短路径问题已经被应用到GIS、GPS等信息管理系统中，为人们生活带来了很大便利。它属于图结构问

2、题，其解决方法也有不少（如Dijkstra、A-star）。单源点最短路径问题解决的是既定起点的情况下，寻求该点到图中其它顶点的最短路径。请用C/C++语言的结构体、指针、数据结构等基础知识，编写程序实现图的结构定义、图的存储，以及求解单源点最短路径。设计过程以及写作要求如下：（1）要针对本题目，认真研究所设计的内容，用简明扼要的语言描述课题，给出课题的基本内容及要求；（2）根据数据结构的相关知识给出实现建立任意m个顶点n条边的图算法、按照用户给定的源点和目标点，求出它们间的最短路径（打印出来）算法的基本策略及思路；（3）给出较为详尽数据结构与算

3、法，算法可以用流程图、伪代码等描述手段进行描述；（4）给出一个完整的算法实现的C/C++程序，算法中的各子算法要力求用函数来实现；（5）对编写的程序要进行详尽的测试分析；（6）对本课题的设计工作要进行一个完整深刻的总结。最终设计成果形式为：1、设计软件一套；2、撰写一份课程设计说明书一份，打印并装订成册。指导教师（签字）：教研室主任（签字）：批准日期：年月日摘要本系统以VC++作为软件开发环境，C语言作为程序开发语言，邻接矩阵作为存储结构，设计与实现了最短路径运算。该系统实现了有向图的存储、最短路径的运算等主要功能。依照该系统可以解决生活中许多问

4、题，比如交通路线的选择，工程时间的预算等等，让人们可以做出合理的选择。本系统通过分析课题的背景、意义、要求，分别从课题描述、逻辑设计、算法设计、调试与测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。界面清晰，操作简单，易于用户接受。关键词：VC++;邻接矩阵;最短路径目录1课题描述12问题分析与任务定义22.1问题分析22.2任务定义23算法设计33.1图的邻接矩阵的存储结构33.2Dijkstra算法思想44系统逻辑设计54.1主函数流程图如图4.1所示54.2Create函数流程图如图4.2所示64.3Dijks

5、tra函数流程图如图4.3所示85源代码116调试与测试146.1合法数据输入146.2非法数据输入15总结16参考文献171课题描述乘车旅行的人大多数都希望找出到目的地尽可能短，花费少的行程，那么如何找出从出发点到目的地的最短路径？由于路径比较多，所以用手工计算起来比较复杂，抽象，因此人们用计算机语言代替手工计算来求得最短路径。而在计算机语言中迪杰斯拉算法比较常用，简捷，故人们经常借助计算机程序用迪杰斯拉算法求得单源点的最短路径，这样可以广泛的提高效率，而且条理清晰，通俗易懂。02问题分析与任务定义2.1问题分析本系统是要解决的是单源点最短路径

6、问题，设计程序，实现最短路径的求法，系统需要达到的主要功能如下：(1)编写算法能够建立带权图，并能够用Dijkstra算法求该图的最短路径。(2)能够选择图上的任意一顶点做为开始节点。最短路径输出不必采用图形方式，可顶点序列方式输出。(3)根据课设题目要求，拟将整体程序分为三大模块。两个子模块相互独立，没有嵌套调用的情况，在主模块中调用上面两个子模块。2.2任务定义根据课设题目要求，拟将整体程序分为三大模块。两个子模块相互独立，没有嵌套调用的情况，在主模块中调用上面两个子模块以下是三个模块的大体分析：(1)建立有向图的存储结构。(2)应用Dijk

7、stra算法求出该有向图的最短路径。(3)在主函数中调用两个子函数，完成最短路径的程序设。13算法设计3.1图的邻接矩阵的存储结构一个图的邻接矩阵表示唯一的。故在图的邻接矩阵表示中，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点vi的信息。本设计是基于类C语言的算法描述，因此，图的邻接矩阵的存储结构定义如下:#defineMVNum50typedefstruct{VertexTypevexs[MVNum];Adjmatrixarcs[MVNum][MVNum

8、]；}Mgraph;在本系统中，以邻接矩阵存储有向图，如图3.1a中有向图G所示，其邻接矩阵为图3.1b所示：图3.1bG的邻接矩阵∞∞