SPFA以及其优化

「爱情、让人受尽委屈。」 2022-09-29 14:56 137阅读 0赞

SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。

SPFA，要从Bellman-ford的优化说起。在n个点m条边的图中，Bellman-ford的复杂度是n\*m，依次对每条边进行松弛操作，重复这个操作n-1次后则一定得到最短路，如果还能继续松弛，则有负环。这是因为最长的没有环路的路，也只不过是n个点n-1条边构成的，所以松弛n-1次一定能得到最短路。

SPFA的意义在于，**如果一个点上次没有被松弛过，那么下次就不会从这个点开始松弛。每次把被松弛过的点加入到队列中，就可以忽略掉没有被松弛过的点。**  
  
但是最外层的循环还是n-1次。如果把被松弛的点放到前边，他相当于没有进行完这一轮松弛，就开始了一些其他的操作。但是这些其他的操作可能是无用的，因为这些操作的起始点可能还会被这一轮松弛更新。

所以传统的SPFA的复杂度不会超过n\*m，并且每个点都不会第n次入队。但是SLF优化...其实就不是个优化..它丢掉了一轮一轮松弛的这个特性..导致复杂度可能呈指数级上升。

其实那个SLF优不算是优化？只是在某些图上可能会更好，但是可以通过直接构造图将其由原本spfa最坏的n\*m的复杂度卡成2^n复杂度了...

这是有可能的。[HDU 4889][]就是这样的题。题目让你造数据卡SPFA。

SPFA出自民科。一般流传的版本O(k\*E)复杂度中有常数就足以证明这一点。原始论文中k并非常数，不能当作常数对待，也就是说什么都没证明。

算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。

这个算法，简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法。

SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的时间复杂度内**求出源点到其他所有点的最短路径**，**可以处理负边**。SPFA的实现甚至比Dijkstra或者Bellman\_Ford还要简单：

步骤：  
设Dist代表S到I点的当前最短距离，Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+∞，只有Dist\[S\]=0，Fa全部为0。

维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。

每次迭代，取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断Dist\[v\]+len是否小于Dist\[u\]，若小于则改进Dist\[u\]，将Fa\[u\]记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。若一个点入队次数超过n，则有负权环。

**SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，**也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的情况，k在2左右。

SPFA算法（Shortest Path Faster Algorithm），也是求解单源最短路径问题的一种算法，用来解决：

给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。 SPFA算法是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算，他的基本算法和Bellman-Ford一样，并且用如下的方法改进：

1、第二步，不是枚举所有节点，而是通过队列来进行优化 设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

2、同时除了通过判断队列是否为空来结束循环，还可以通过下面的方法： 判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）。

**SPFA算法有两个优化算法 SLF 和 LLL：**

**SLF**：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾。

**LLL：**Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。 SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。 在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。

具体请看：[点击打开链接][Link 1]

[HDU 4889]: http://acm.hdu.edu.cn/showproblem.php?pid=4889
[Link 1]: http://www.nocow.cn/index.php/SPFA