基于Dijkstra算法求有向带权图的最短路径.doc

《基于Dijkstra算法求有向带权图的最短路径.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、湖北大学本科学年论文题目单源最短路径算法分析与研究姓名夏臻学号2012221104230007专业年级2012级信息安全指导教师马传香职称教授成绩2014年12月02日目录一、摘要1二、最短路径22.1最短路径的定义22.2最短路径解决算法32.2.1Dijkstra算法32.2.2A*算法32.2.3SPFA算法32.2.4Bellman-Ford算法32.2.5floyd-warshall算法4三、Dijkstra算法实现单源最短路径43.1最短路径的最优子结构性质43.2Dijkstra算法思路43.3Dijkstra算法描述5四、Dijkst

2、ra算法测试64.1测试数据64.2运行结果6五、心得体会6六、参考文献7七、附录8第12页共13页一、摘要最短路径问题是图论理论的一个经典问题。寻找最短路径就是在指定的网络中两节点间找到一条距离最小的路。最短路径算法的选择与实现是通路设计的基础，是计算机与信息科学等领域研究的热点问题。很多与时间、费用、线路容量等许许多多的实际问题都要运用最短路径的算法原理来解决，生活中很多的问题的解决离不开这些算法，随着计算机结构的改变以及数据结构的研究与发展，新的有效的算法不断涌现。本文是来对最短路径的算法包括Dijkstra算法、Floyd-Warshall算

3、法、Bellman-Ford算法、SPFA快速算法做一些分析和研究。分析这几种算法的目的在于更好的理解求解单源最短路径问题解题思路，从而尝试着是否能研究出更好的算法。。关键词：单源最短路径图论Dijkstra算法Floyd-Warshall算法Bellman-Ford算法SPFA算法二、最短路径2.1最短路径的定义最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：第12页共13页1.确定起点的最短路径问题-即已知起始结点，求最短路径的问题2.确定终点的最短路径问题-与确定起点的问题

4、相反，该问题是已知终点结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题就等同于把所有路径方向反转的确定起点的问题。3.确定起点终点的最短路径问题-即已知起点和终点，求两结点之间的最短路径。4.全局最短路径问题-求图中所有的最短路径。2.2最短路径解决算法2.2.1Dijkstra算法迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。2.2.

5、2A*算法A*算法；A*（A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好。2.2.3SPFA算法SPFA（ShortestPathFasterAlgorithm）算法是求单源最短路径的一种算法，在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。2.2.4Bellman-Ford算法第12页共13页Bellman-ford算法是求含负权图的单源最短路径算法，效率很低，但代码很容易写。即进行不停地松弛（原文是这么写的，为什么要叫松弛，争议很大）

6、，每次松弛把每条边都更新一下，若n-1次松弛后还能更新，则说明图中有负环，无法得出结果，否则就成功完成。Bellman-ford算法有一个小优化：每次松弛先设一个标识flag，初值为FALSE，若有边更新则赋值为TRUE，最终如果还是FALSE则直接成功退出。Bellman-ford算法浪费了许多时间做无必要的松弛，所以SPFA算法用队列进行了优化，效果十分显著，高效难以想象。SPFA还有SLF，LLL，滚动数组等优化。2.2.5floyd-warshall算法Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。通常可以在任何图中使

7、用，包括有向图、带负权边的图。三、Dijkstra算法实现单源最短路径3.1最短路径的最优子结构性质该性质描述为：如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离，那么必定存在另一条从k到s的最短路径P'(k,s)，那么P'(i,j)=P(i,

8、k)+P'(k,s)+P(s,j)