几种最短路径算法的比较.doc

几种最短路径算法的比较
（陈先红　湖北省仙桃市沔城高级中学）

摘 要：最短路径算法种类繁多，比较有名的算法包括：Dijkstra 算法、Warshall –Floyd算法、动态规划算法、A*算法以及改进的Dijkstra 算法，而即使同一种算法也有多种不同的实现方式。本文主要这几种经典的算法进行分析比较。
关键词：最短路径 算法 邻接矩阵
1. 引言
所谓最短路径问题就是指在带权值的地图中, 寻找从指定起点到终点的一条具有最小权值总和的路径问题。如果把权值看成是道路的长度属性, 那么目标路径就是从起点到终点的最短路径。所谓最短路径就是网络中两点之间距离最短的路径，这里讲的距离可以是实际的距离，最短路径不仅仅指一般地理意义上的距离最短,也可以引申为其它的度量，如时间、运费、流量等。
2. Dijkstra算法
设源点为，目标点为。Dijkstra算法的基本思想是：按距离由近到远为顺序，依次求得到G的各顶点的最短路和距离，直至，算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。
算法步骤如下：
步骤1：令=0，对于，令，，。
步骤2：对每个，用代替，
当不相邻时，。计算，把达到这个最小值的一个顶点记为，令。
步骤3：若，则停止；若，则代替，转步骤2。
3. Warshall -Floyd算法
每次以一个顶点为源点，重复执行Dijkstra算法N次。但这里要提的Warshall -Floyd算法形式上相对简单一些。
Warshall -Floyd算法的基本思想：
对于任何一个顶点，顶点到顶点的最短路径经过顶点或者不经过顶点。比较与的值。若，则令，保持是当前搜索的顶点到顶点的最短路径。重复这一过程，最后当搜索完所有顶点时，就是顶点到顶点的最短距离。
Warshall -Floyd算法的基本步骤：
令是顶点到顶点的最短距离，是顶点到顶点的权。Warshall -Floyd算法的步骤：
步骤1 输入图G的权矩阵W。对所有，有=，。
步骤2 更新。对所有，若，则令。
步骤3 若，则存在一条含有顶点的负回路，停止；或者
停止，否则转步骤2。
4. 动态规划算法
动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。动态规划算法使用于解最优化问题。通常可以按以下步骤设计动态规划算法：
（1）找出最优解的性质，并刻画其结构特征；
（2）递归地定义最优解；
（3）以自底向上的方式计算出最优解；
（4）根据计算最优值时得到的信息，构造最优解。
5.A* 算法
A*算法是在宽度优先搜索算法的基础上, 每次都是利用一个自己确定的估价函数对所有没展开的结点进行估价,从而找出最应该被展开的结点（也就是说要找的答案最有可能是从该结点展开,把该结点展开,直到找到目标结点为止）。
A* 算法是人工智能领域的一种图搜索策略, 采用了启发式函数对搜索过程中产生的分支进行评估, 以选择最佳的分支进行搜索。其更一般的引入了一个估价函数f(n),其定义为f(n)=g(n)+h(n)。 其中g(n)为到达当前节点的耗费, 而h(n)表示对从当前节点到达目标节点的耗费的估计, 其必须满足两个条件：
(1) h(n)必须小于等于实际的从当前节点到达目标节点的最小耗费h*。
(2) f(n)必须保持单调递增。
A* 算法生成的总节点数为N ,解的深度为d ,尝试为d 的一致搜索树为了包括N + 1 个节点所必须的分支因子为b* 。因此, ,可以看出空间复杂度高。如果是可采纳的,即启发函数设计得好, 可以大大降低扩展的节点,从而在较小的时间内即可完成最佳路径搜索。其时间复杂度为。
6.改进的Dijkstra 算法
传统的利用Dijkstra 算法来实现图中任意结点之间的最短路径查找,其基本思想就是依次以图中各个结点为起点利用Dijkstra 算法计算出最短路径,这样循环n 次即可得到图中任意结点之间的最短路径,而每一步都是一个简单的重复过程。这样虽然能够实现任意两点之间的最短路径查找,但是从效率上分析并不是最优的。实际是可以进行改进,具体方法如下:
（1） 根据Dijkstra 算法思想,可以由图中结点的出入度信息来提高各点之间最短路径的查找速度。
（2） 在带权图中利用Dijkstra 算法找出部分结点之间的最短路径后,若其他还没有找出最短路径的结点可以利用前面已找出的最短路径信息为自己提供快速的最短路径查找。
7.最短路径算法的分析比较
求解同一计算问题可能有许多不同的算法,究竟如何来评价这些算法的好坏,主要考虑两点：
（1）执行算法所耗费的时间;
（2）执行算法所耗费的存储空间。
7.1 Dijkstra 算法的成功率是最高的，因为它每次必能搜索到最优路径。但另一方面， Dijkstra 算法的搜索速度是最慢的。Dijkstra 算法求一个点到其他所有点的最短路径时间复杂度为，求一个点到其他所有点最短路径等效于求一个点到另一个点的最短路径n 个点之间互相的最短路径空间复杂度为。
7.2 Warshall -Floyd算法基于图论的矩阵理论,是非常有特点的一个传统算法。该算法可以方便的计算每对顶点之间的最短路径和长度。时间复杂度为。
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；
缺点：时间复杂度比较高，不适合计算大量数据。
7.3　动态规划算法主要是求解最优决策序列, 当最优决策序列中包含最优决策子序列时, 可建立动态规划递归方程, 它可以帮助高效地解决问题。用动态规划方法不仅能得到全局最优结果，还能得到一族最优结果。有了这一族最优结果，便于分析、比较不同的结果，且如果由于某种原因偏离了原始最优轨迹，也可以很方便地找出余下阶段的新的最优子策略。
7.4A* 算法 空间复杂性：A* 算法生成的总节点数为N，解的深度为d，那么b* 就是尝试为d 的一致搜索树为了包括N+1 个节点所必需的分支因子。因此，N+1=1+b*+（b*）2+…+(b*)d，从中可看出空间复杂度高。
时间复杂性：充分利用问题内在信息，启发函数设计的好，可以极大降低扩展的结点,从而在较小的时间内即可完成最佳路径搜索。如果是可采纳的，那A* 算法是完备的也是最优的。
7.5 改进的Dijkstra算法
在改进算法中, 初始时, 待排序的节点以无序形式连续序存放在一个一维数组中, 对其进行堆排序, 调整成小顶堆后, 各节点即是以完全二叉树的顺序存储结构形式存储, 0 号单元存放的即是调整后的堆顶元素, 后面依次以左子树、右子树。在调整堆的过程中时间复杂度为 , ( N 为待排序节点个数) 。与从无序结构下的数组或链表中选择下一个最短路径节点相比较, 明显地节约了时间, 提高算法执行效率。Dijkstra 优化算法在搜索的路径节点总数及算法运行时间方面均明显减少也就是说, 使用优化的算法从源点经过较少的节点就可到达终点,且能够更加快速的趋于目标节点。

参考文献
[1]严蔚敏.数据结构（C语言版）[M].北京：清华大学出版社，1997
[2]王海英,黄强,李传涛.图论算法及其MATLAB实现[M].北京：北京航空航天大学出版社，2010
[3]周先曙．最短路径问题及其解法研究[J]．电脑知识与技术，2010，（06）
[4]方美红,刘少华. 基于vc++最短路径算法设计与实现[J] .城市勘测，2008，（01）

作者：陈先红　湖北省仙桃市沔城高级中学 433014 联系电话：[phone]
4