几种经典的最短路径算法比较分析

打开文本图片集

摘要：最短路径问题是图论和复杂网络中的经典问题之一，在现实生活中具有广泛的应用.基于此，对最短路径问题进行了系统分析，阐述了几种经典的最短路径算法：Dijkstra算法、Floyd算法、Bellman-Ford算法和SPFA算法，并对这几种最短路径算法的时间复杂度和算法适用情况进行了全面的对比分析.

关键词：最短路径;Dijkstra算法;Floyd算法;Bellman-Ford算法;SPFA算法

中图分类号：TP301.6  文献标识码：A  文章编号：1673-260X（2018）12-0047-03

0 前言

最短路径是图论与复杂网络分析中的一个经典问题[1]，在工程规划、地理信息系统、通信和军事运筹学等领域有着十分广泛的应用[2].最短路径问题的目的是寻找图中两结点之间的最短路径，也就是沿此路径上各边的权值总和（路径长度）达到最小[3].近年来，最短路径问题在交通网络、通信网络、厂区布局、旅游路线推荐等实际生活中具有广泛的应用，引起了交通、物流、运筹学、管理学、计算机科学等多领域广大学者的关注，涌现出多种经典的最短路径算法以及相应改进算法.这些算法在空間复杂度、时间复杂度、易实现性及应用范围等方面各具特色[4-6].文献[7]给出了一种改进的Dijkstra标号算法，有效解决了连通无向带权图和有向带权图的最短路径问题，文献[8]对Dijkstra算法进行了改进，有效解决多邻接点问题与多条最短路径问题，文献[9]提出的基于Floyd算法的改进算法可以有效解决多重等价最短路问题，文献[10]通过对固定序Bellman-Ford算法进行修正，获得了一种求解边数不大于k的最短路问题的新算法，文献[11]给出了改进的SPFA算法，降低了算法的时间复杂度，使得对于任意的有向图，该算法都能够在O（"V||E|）内执行完毕.这些最短路径算法各有其优势，适应于不同网络结构.本文全面地分析了最短路径问题，对Dijkstra算法、Floyd算法、Bellman-Ford算法、SPFA算法几种经典的最短路径算法给出全面的阐述，并采用Java语言设计了一个实验系统，对这几种经典算法进行验证实验，并比较这几种经典的算法在不同网络中的运行时间和运行结果，此外，还对每种算法的适用性进行了分析.

1 相关定义

1.1 图

在一个由n个节点和m条边组成的图G（V，E）中，V代表G中所有顶点集合，E代表G中所有边集合，对稠密图的定义是有较多条边或弧的图（如e

1.2 最短路径

最短路径问题是求由源点vs到达图中任一顶点的最短路径，即寻找一条路径，使得这条路径上的边的权值总和∑Wij为最小值.最短路径问题分为静态和动态等多种形式：静态路径是指在外界环境不变的基础上，计算最短路径;而动态路径是指外界环境不断发生变化，在不能预测的情况下计算最短路径[7].

1.3 松弛

松弛操作即如果图中两点之间存在其他路径，并且该路径的距离小于这两点之间的当前距离，那么这两点之间的最短路径长度更新为这个更小的距离.若图中存在顶点无法再进行松弛操作，则称该顶点已收敛.在图1中，a点到b点的距离原本为5，但由于从a点出发经由c点也能到达b点，并且eac+ecb=1+2=3<5，即新路径的距离小于原始路径距离，因此将A点到B点之间的距离更新为3，此时图中各点均已收敛.

2 最短路径算法

2.1 Dijkstra算法

Dijkstra[14]算法基于贪心策略.首先，每次找到离源点最近的一个顶点，确定源点到该点之间的最短路径，然后，检查是否能通过该顶点进行松弛操作，最后，得到源点到其他各个顶点之间的最短路径.

Dijkstra算法的具体步骤如下：

（1）将图中所有顶点分为P和Q两个集合：P是已知源点到其他顶点的最短路径的顶点集合，Q是未知最短路径的顶点集合，设置源点到自身之间的距离为0，源点与能直接到达的顶点之间的距离为该边权值w，同时把源点不能直接到达的顶点的之间的距离设置为无穷大;

（2）把源点置于P中，表示已求得源点到自身的最短路径;

（3）遍历Q，找出距离源点最近的顶点vi，将顶点vi置于P中，表示以求得源点到顶点vi之间的最短路径.并考察源点到Q中保留的顶点之间是否能通过源点到vi之间的最短路径松弛，如果有未收敛的顶点则进行松弛操作;

（4）重复第（3）步，直至Q为空，算法结束，求得源点到图中所有顶点之间的最短路径.

2.2 Floyd算法

Floyd算法[2]是一种动态规划算法.对于G中包含的边eij，从任意节点vi到任意节点vj的最短路径d[i，j]只存在两种可能：（1）直接从vi到vj，此时dij=eij;（2）从vi经过若干个节点到vj.对于每个节点vk，检查dij>dik+dkj是否成立，若成立，则令dij=dik+dkj[6].由此得到状态转移方程：dij=min{dij，dik+dkj}.

Floyd算法的具体步骤如下：

（1）从图G任意一个节点vk开始，遍历图中所有边eij，检查是否满足dik+dkj<dij，如果成立，说明从节点i到节点k再到节点j的路径要短于直接从节点i到节点j的路径，故进行松弛操作，更新dij=dik+dkj;

（2）重复步骤（1），直至遍历完图中所有节点，dij中记录的便是节点i到节点j的最短路径距离.

2.3 Bellman-Ford算法

Bellman-Ford算法[14]通过递推迭代方式反复对边集E中每条边进行松弛操作，使得源点到其他每个顶点u∈V的最短路径估计值逐渐逼近其最短距离.Bellman-Ford算法最多有n-1个阶段，在每一个阶段，都需要循环遍历图中的每一条边进行松弛操作.在前k个阶段结束后，求得从源点最多经过k条边到达其他所有顶点的最短路.n-1个阶段结束后，就求得了源点最多经过n-1条边到达其他顶点的最短路径.由于最短路径问题是不包含回路的，所以经过n-1条边得到的最短路径就是源点到其他顶点的最短路径的确定值.

Bellman-Ford算法的具体步骤如下：

（1）初始化所有点到源点之间的最短距离.将源点到自身的距离设置为0，源点到其他点的距离设置为无穷大（表示不可达）;

（2）对边集E中的每条边进行循环遍历，进行松弛操作，循环最多需进行n-1次;

（3）检测边集E中的每一条边的两个断点是否收敛.如果存在未收敛的顶点，则说明图中存在负权回路.

2.4 SPFA算法

SPFA[15]算法采用动态逼近法，通过控制顶点的松弛顺序来优化Bellman-Ford算法.在Bellman-Ford算法中，松弛过的顶点顺序会影响之后顶点的松弛顺序，只有那些在上一次松弛中改变了最短路径估计值的顶点，才可能引起与该顶点相邻的顶点最短路径估计值发生改变.因此，用一个先进先出的队列来保存被松弛过的顶点，之后只处理队列中的顶点，以此来降低算法的时间复杂度.

SPFA算法的具体步骤如下：

（1）初始化，将源点加入队列;

（2）进行迭代，每次取得队列的队首节点，将所有与队首节点相邻的顶点进行松弛操作，若松弛成功，则查看进行松弛操作的顶点是否在队列中，若不在将该顶点加入队列中;

（3）反复从队列里取出点来对当前最短路径进行优化，直至队列为空不需要再优化为止.

3 最短路径算法的比较分析

Dijkstra算法中计算两点之间最短路径时一共需要两次循环，因此时间复杂度为O（N2）.Dijkstra算法適用于稠密图，并且只能适用于边权都为正的图，不能解决负权图的最短路径问题.其原因是根据Dijkstra算法的求解思想，集合Q中与源点之间的距离最近的顶点vi即为源点到该点的最短路径，但如果图中有负权边，有可能源点通过其他顶点到达vi的距离比源点直接到达顶点vi的距离更小.

Floyd算法的时间复杂度为O（N3），空间复杂度为O（N2）.对于稠密图，效率要高于执行n次Dijkstra算法，也要高于执行n次SPFA算法.Floyd算法适用于多源最短路径，可以算出任意两个节点之间的最短距离，适用于稠密图，和顶点关系较为密切，并且可以解决负权边的问题，且编码较为简单.但时间复杂度比较高，不适合计算大量数据.

Bellman-Ford算法最多需要执行n-1次循环，每次循环需要遍历图中所有边，因此时间复杂度为O（（n-1）*m）=O（nm），由于采用边集数组存储边的信息，Bellman-Ford算法的空间复杂度为O（m）.Bellman-Ford算法可以解决负权图问题，并可以检查图中是否含有负权回路，适用于稀疏图和边的关系较为密切图.

SPFA算法的平均时间复杂度为O（m），当m<<n2时，SPFA算法表现出时间复杂性上的优越.时间复杂度在最坏情况下也是O（nm）.由于采用边集数组存储边的信息，SPFA算法的空间复杂度为O（m）.SPFA算法的时间效率不稳定，对于不同的图的执行时间有很大的差别.最好情况下，每个节点只入队一次，这时SPFA算法变为BFS广度优先遍历算法，时间复杂度为O（m）.但是在最坏情况下，每个节点都入队n-1次，此时SPFA算法退化为Bellman-Ford算法，时间复杂度为O（nm）.如果某个节点的入队次数超过n次，那么图中肯定含有负权回路.SPFA算法可以解决负权图的最短路径问题，也可以检测图中是否含有负权回路，同样适用于稀疏图和边的关系较为密切图.

对上述算法进行实验，比较各算法在不同网络图中的特性.通过实验得出，不同算法之间有着不同的特性，Dijkstra算法只能适用于边权都为正的图，不能解决负权图的最短路问题，适用于稠密图，和顶点关系密切.Dijkstra算法最大的弊端是它无法适应有负权边的图.而Floyd算法、Bellman-Ford算法和SPFA算法都可以解决负权问题，其中Floyd算法适用于稠密图，和顶点关系较为密切.Bellman-Ford算法和SPFA算法都适用于稀疏图，和边的关系较为密切.这几种算法的区别详见表1.

4 结论

近年来，随着复杂网络研究的不断进步，最短路径问题作为复杂网络优化中应用比较广泛的问题之一，引起了广大研究学者的关注.最短路径问题的涉及互联网通信、交通运输等多个应用领域，对该问题的研究与分析就具有重要的理论意义和实际意义.本文深入分析了几种经典的最短路径算法，首先，对这几种最短路径算法的核心思想与算法流程进行完整的描述;然后，对这几种经典最短路径算法进行全面的比较分析通过实验对比，我们得出SPFA算法不仅适用于负权图，在其他网络图中的实验结果中也显示出较好的性能.

我们的下一步工作，将研究最短路径的改进算法，推广最短路径算法去解决实际应用生活中的问题.

参考文献：

〔1〕付媛，朱礼军，韩红旗.K最短路径算法与应用分析[J].情报工程，2015，1（1）：112-119.

〔2〕张德全，吴果林，刘登峰.最短路问题的Floyd加速算法与优化[J].计算机工程与应用，2009，45（17）：41-43.

〔3〕王树西，李安渝.Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机科学，2014，41（6）：217-224.

〔4〕Deo N， Pang C Y. Shortest-path algorithms： Taxonomy and annotation [J]. Networks， 1984，14（2）：275-323.

〔5〕Cherkassky B V， Goldberg A V， Radzik T. Shortest paths algorithms： Theory and experimental evaluation [J]. Mathematical programming， 1996，73（2）：129-174.

〔6〕Zhan F B， Noon C E. Shortest path algorithms： an evaluation using real road networks [J]. Transportation science，1998，32（1）：65-73.

〔7〕王树西，吴政学.改进的Dijkstra最短路径算法及其应用研究[J].计算机科学，2012，39（5）：223-228.

〔8〕王树西，李安渝.Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机科学，2014，41（6）：217-224.

〔9〕左秀峰，沈万杰.基于Floyd算法的多重最短路问题的改进算法[J].计算机科学，2017，44（5）：232-234.

〔10〕韩伟一，固定序.Bellman-Ford算法的一个改进[J].哈尔滨工业大学学报，2014，46（11）：58-62.

〔11〕夏正冬，卜天明，张居阳.SPFA算法的分析及改进[J].计算机科学，2014，41（6）：180-184.

〔12〕严蔚敏，吴伟民.数据结构：C语言版[M].北京：清华大学出版社，2002.157-158.

〔13〕Dijkstra E W.A note on two problems in connexion with graphs [J]. Numerische mathematik，1959，1（1）：269-271.

〔14〕刘磊，王燕燕，申春，等.Bellman-Ford算法性能可移植的GPU并行优化[J].吉林大学学报（工学版），2015，45（05）：1559-1564.

〔15〕段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报，1994，29（2）：207-212.

推荐访问:几种 最短 算法 路径 经典