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所示七、 程序源代码#include void main() int infinity=100,j,i,n,k,t,*w,*s,*p,*d; coutn; coutendl; d=new intn; s=new intn; p=new intn; w=new int*n; for(i=0;in;i+) wi=new intn; for(i=0;in;i+) for(j=0;jwij; for(s0=1,i=1;in;i+) si=0;di=w0i; if(diinfinity) pi=0; else pi=-1; for(i=1;in;i+) t=infinity;k=1; for(j=1;jn;j+) if(!sj)&(djt) t=dj;k=j; sk=1;/point k join the S for (j=1;jdk+wkj) dj=dk+wkj;pj=k; cout从源点到其它顶点的最短距离依次如下：; for(i=1;in;i+) coutdi ; 八、程序运行结果九、设计结果分析 它是运用贪心的算法不断添加点从而到达终点。建立一个集合，在代码中可以用来标记一下就可以。这个集合的初始时只有起点，我们把从源到u且中间只经过S中顶点的路程为从源到u的特殊路径，并用dist数组记录当前每个顶点所对应的最短特殊路径。Dijkstra算法从源出发，达到直接相连的点i，设为一层点，并把disti赋为其权值。然后再检查与这几个点（除源点）相连的点，设为二层点，二层点中可能有一层点,比较一下源点直接到该点的路程和源点间接到达该点路程，修改dist，直到找到终点。十、设计总结(1) “按路径长度递增顺序”是因为，扩展下一个永久标记节点总是从U中节点的邻接节点中找到。(2) 虽然我们要求的是v0到某个目标节点的最短路径，但是在查找这条路径的过程中，我们可能附带的把顶点到其他节点的最短路径也求出来了。(3) Dijkstra算法包括N-1次的外层循环（每次循环找到起点到其中某个结点的最短路径）和两个内层循环，第1个内层循环要经过N次比较来完成对所有结点权值的调整，第2个内层循环从所有结点中找出权值最小的未标记结点，并置于U中，此循环也需要经过n次比较以找到符合条件的结点。Dijkstra算法的时间复杂度为O(n2)。(4) 以邻接矩阵为存储结构的Dijkstra算法是经典的最短路径算法；但是，该算法的实现需要耗费大量的时间和存储空间。目前，已有不少改进算法。比如采用邻接链表作为存储结构，并且为了加快搜索速度，根据距起点的最短路径的权值构造一优先级队列，按照权值大小由小到大排序。另外，从搜索范围角度考虑，Di