Dijkstra最短路径算法-课程设计.doc

课 程 设 计 任 务 书 一、课程设计题目： 求最短路径算法的实现 二、课程设计主要参考资料 （1）严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2006 （2）徐凤生,李天志.所有路径的求解算法[J].计算工程与科学,2006,28(12):83-84 （3）王志和,凌云.Dijkstra最短路径算法的优化及实现[J].软件时空,2007,23(11):275-277 三、课程设计拟解决的主要问题： （1） 最短路径的概念及算法介绍 （2） Dijkstra算法的基本思想和原理及实现 （3） （4） 四、课程设计相关附件（如：图纸、软件等）： （1） Microsoft Visual C++ 6.0 （2） 五、任务发出日期： 2010-6-14 课程设计完成日期： 2010-6-28 指导教师签字： 教研室主任签字： 指导教师对课程设计的评语 成绩： 指导教师签字： 年 月 日 Dijkstra算法简介 　　Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 　　Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 　　Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。 Dijkstra算法思想 迪杰斯特拉(Dijkstra)算法是用来求解有向图的最短路径问题的经典算法.它的基本思想是,从一个起点出发,依次寻找到起点最近的结点.每找到一个结点,就放进一个闭表中,并在寻找结点的过程中,记录起点到各点的最短路径.起点到各点的最短路径不是一成不变的.它随着搜寻的深入不断修改更新.比如从v0到v1初始时距离为30,此为它初始时的最短距离,{v0, v1}也为v1的最短路径.而搜寻到v2时, v0-v2=10, v2-v1=5; 即v0-v3-v2=15;此时v0到v1的最短距离就被更新为15,其最短路径也变为{v0, v2, v1}. 当然,后面还有可能存在v0-v7-v9-v8-v999-v1 = 10这样更短的路径. 当整张图搜索完毕时,所有顶点到起点的最短路径也就确 Dijkstra算法具体步骤　　 　　创建两个表，OPEN, CLOSE。 　　OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。 　　1． 访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。 　　2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。 　　3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。 4． 重复第2和第3步,直到OPEN表为空，或找到目标点。 Dijkstra算法的流程图 六、项目设计内容： 通过设计一个C++ 程序，运用D算法，用以求各个节点直接的最短路径最后利用程序求得节点到各个节点之间的最短路径。设计节点图如图-1所示 程序源代码 #includeiostream.h vo