三种最短路算法的比较

赵美勇　宋思睿

摘要：在图这个数据结构中，最常见的一种问题就是求这个图中的给定的起点和终点来找到一条最短的路径，这不光是计算机的一个问题，同时也是现实生活中可能需要考虑的事情。现在的各大地图应用，核心算法都是利用的最短路算法，最短路算法有很多种，但是有三个最有名的最短路算法：Floyd、Dijkstra、SPFA，对于这三种算法的使用场景，则是根据算法的复杂度来决定。因此，将这三种算法在复杂度、优化方面进行了比较。

关键字：Floyd Dijkstra SPFA时间复杂度 图

1 Floyd算法

Floyd最短路算法是基于动态规划思想的一种算法。它的动态转移方程f[i，j]=min（f[i，j]，f[i，k]+f[k，j]），其算法的具体过程：

（1）定义一个二维数组f，f[i，j]表示从i到j的最短距离，在初始化时，将数组用最大值填充。

（2）根据图中的点数n，然后进行三层枚举，枚举的顺序为k、l、j，其中k作为枚举到的中间节点，i、j分别代表起点和终点，因此它的转移方程f[i，j]=min（f[i，j]，f[i，k]+f[k，j]）表示为，从i到j的距离是否可以被经过中间节点k组成的i到k再到j的路径更新，因为找的是最短路径，所以选用的mm函数，如果f[，k]+f[k，j]小于f[i，j]，则更新f[i，j]，反之则不更新。

（3）整个f数组储存的都是对应点的最短距离，按照要求输出结果。

根据整个算法的描述，可以看出算法的核心是处理转移方程的三重循环，因此Floyd算法是立方级别的，所以Floyd算法在处理图比较大的情况时并不适用，它适用一些图比较小的情况。同时Floyd算法可以拓展，多一层内循环可以衍生出一个新算法就是寻找图中的最小环。

2 Dij kstra算法

Dijkstra算法是求单源最短路径的一种算法，即最短路的起始点唯一。Dijkstra算法是一个基于贪心的一种算法，其整个算法的过程：

（1）确定起点定义一个数组dist[i]，表示从起点到i点的最短距离，再定义一个数组flag[i]用来表示i这个点是否被遍历过。

（2）输入图矩阵，初始化dist数组，如果点i与起始点有边相连，那么dist[i]的值为他们的边权，如果没有边相连，则值为无穷大;对于flag数组的初始化，将起始点标注为1，表示为访问过，将其他的没有访问过的置为O。

（3）遍历n-l次，表示的是更新n-l次，因为在初始化时已经将起始点处理好了。每一次循环，找到當前距离起始点最近且没有被访问过的点，将这个点标记为访问过，然后用这个点去更新当前的最短路，具体的松弛操作语句为：dist[i]=min（dist[dist[i]+map[i，j]），和Floyd算法的转移方程基本一致。贪心的思想体现在，每次都找当前没有访问过且距离最小的点来进行下一次迭代。

根据整个算法描述，可以看出整个算法的核心循环是遍历每一个没有被访问过的点，再找到当前结点的最小点，利用这个最小点来更新其他的点。因此算法的复杂度是平方级别的，但是我们可以注意其中一个步骤，我们再找当前点的最小点的时候可以利用堆来维护一个序列，堆顶就是最小值，虽然优化之后的算法复杂度仍是平方级别，但是在某些情况下可能会被卡常数，因此可以利用这个堆优化。

3 SPFA算法

SPFA算法的全称为Shortest Path Faster Algorithm，即最短路更快算法。SPFA是Bellman-Ford算法的一种队列优化，是一种基于BFS的最短路算法，该算法解决了Dijkstra算法无法解决的变权为负值的情况，防止负环的情况导致算法永远迭代进入死循环，SPFA的关键一点是图的存储，一种是邻接表，另外一种边集数组，又被叫做前向星优化，整个算法的过程，这里选取边集数组：

（1）确定起点，定义七个数组分别为：head[i]表示起点为i的边的序号，dist[i]表示从起点到点l的最短距离，v[i]表示第i条边指向的点，w[i]表示第i条边的权重，next[i]表示第i条边所连接的另一条边的边序号，q数组表示队列，flag[i]表示点l是否被访问过。

（2）首先将dist和flag数组进行初始化，将dist数组初始为无穷大，再将flag初始为false。读入起点和终点，将起点入队，然后将起点的距离置为O，。

（3取出队首数据并将其flag置为O遍历所有以该点为起点的边，获得改边所指向的点，然后进行松弛，如果当前这个点没有被访问过，则将其入队，并且将其访问标志置为l，等迭代完成，当前的dist数组中所存放的均为最短距离。

根据整个算法描述可以看出算法的核心就是对于队列的操作，即为每个点进入队的次数，因此它的时间复杂度为O（VE），其中V为每个点的入队次数，E表示边的数量。但这是平均时间复杂度，最坏的情况，即一个点连接所有的点，此时复杂度最高，和Dijkstra的复杂度一样高。SPFA在处理负边权时，已经入队的点无法再次人队，只能等待该点在队列中取出才能再次入队，这样就防止了一个负变权可以无限的震荡。由于SPFA利用了队列，则根据队列的性质，SFPA出现了多种优化：SLF优化和LLL优化等。

4三种算法的比较

这三种算法适用于不同的环境，对于第一种Floyd算法，它求的是多源最短路，可以得到任何两个点的最短路径，但是相应的复杂度最高，这种算法比较适用于点不是很多，但是边有很多的图。对于第二种Dijkstra，它是最稳定的一种最短路算法，基本所有有关最短路方面的算法都是它的变体，它的复杂度比第一种少了一个数量级，但是它的算法的优化很少，最常见的即为堆优化，维护每次迭代取出的最小点。第三种是SPFA，它是争议最大的算法，这个算法最初由西南交通大学的段凡丁证明并提出的，后来证明段凡丁是错误的，SPFA就是Bellman-Ford的队列优化的形式，但对稠密图，SPFA的表现要比Dijkstra出色。

5总结

通过对于这三种算法的时间复杂度的分析，以及相应的优化，还有所适用的环境讨论，可以得出在图的最短路中，最重要的就是迭代求解的过程，如何优化这个过程才是减少时间复杂度的关键，而只是更新进队入队、维护最小点数组，这些只能是解决一些卡常数的问题。因此，仍然需要更多的知识来优化核心的迭代。

参考文献

[1]Thomas H.Cormen， Charles E.Leiserson， Ronald L.Rivest，Clifford Stein.算法导论[M].殷建平，徐云，王刚，刘晓光，苏明，邹恒明，王宏志，译.北京：机械工业出版社，2012.

[2]Robert SedgeWick，Kevin Wayne.Algorithms.算法（第4版）[M].4thed.谢路云，译.北京：人民邮电出版社，2012.

[3]Brian W. Kernighan， Dennis M. Ritchie.The C ProgrammingLanguage[M].2nd ed.徐宝文，李志，译.北京：机械工业出版社，2004.

[4]刘汝佳，陈锋.算法竞赛入门经典：训练指南[M]，北京：清华大学出版社，2012.

[5]刘汝佳.算法竞赛入门经典.第2版[M].北京：清华大学出版社，2014.