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

赵卫绩，巩占宇，王 雯，樊守芳

（绥化学院 信息工程学院，黑龙江 绥化 152061）

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＜nlogn)，反之称为稀疏图[12].假设顶点之间的距离为w，则图中任意两点之间的距离可以用一个权值矩阵e来表示.设置源点为vs，并将源点到自身的距离设置为0，若两个顶点之间可达，则eij可以表示图中顶点i到顶点j之间的距离，同时把图中不能直接到达的顶点之间的距离设置为无穷大.

1.2 最短路径

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

1.3 松弛

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

图1 松弛操作

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时，SP-FA算法表现出时间复杂性上的优越.时间复杂度在最坏情况下也是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.

表1 最短路径算法比较分析

4 结论

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

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