SPFA算法介绍

大家好，欢迎来到IT知识分享网。

SPFA算法是求解单源最短路径问题的一种算法，由理查德·贝尔曼(Richard Bellman) 和 莱斯特·福特创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达 O(VE)。但算法可以进行若干种优化，提高了效率。
算法的思路：我们用数组dis记录每个结点的最短路径估计值，用邻接表或邻接矩阵来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
我们要知道带有负环的图是没有最短路径的，所以我们在执行算法的时候，要判断图是否带有负环，方法有两种：
1.开始算法前，调用拓扑排序进行判断（一般不采用，浪费时间）
2.如果某个点进入队列的次数超过N次则存在负环（N为图的顶点数）
SPFA算法手动操作过程
下面我们采用SPFA算法对下图求v1到各个顶点的最短路径，通过手动的方式来模拟SPFA每个步骤的过程

初始化：

首先我们先初始化数组dis如下图所示：（除了起点赋值为0外，其他顶点的对应的dis的值都赋予无穷大，这样有利于后续的松弛）

此时，我们还要把v1如队列：{v1}

现在进入循环，直到队列为空才退出循环。
第一次循环：
首先，队首元素出队列，即是v1出队列，然后，对以v1为弧尾的边对应的弧头顶点进行松弛操作，可以发现v1到v3，v5，v6三个顶点的最短路径变短了，更新dis数组的值，得到如下结果：

我们发现v3，v5，v6都被松弛了，而且不在队列中，所以要他们都加入到队列中：{v3，v5，v6}

第二次循环
此时，队首元素为v3，v3出队列，然后，对以v3为弧尾的边对应的弧头顶点进行松弛操作，可以发现v1到v4的边，经过v3松弛变短了，所以更新dis数组，得到如下结果：

此时只有v4对应的值被更新了，而且v4不在队列中，则把它加入到队列中：{v5,v6,v4}

第三次循环
此时，队首元素为v5，v5出队列，然后，对以v5为弧尾的边对应的弧头顶点进行松弛操作，发现v1到v4和v6的最短路径，经过v5的松弛都变短了，更新dis的数组，得到如下结果：

我们发现v4、v6对应的值都被更新了，但是他们都在队列中了，所以不用对队列做任何操作。队列值为：{v6，v4}

第四次循环此时，队首元素为v6，v6出队列，然后，对以v6为弧尾的边对应的弧头顶点进行松弛操作，发现v6出度为0，所以我们不用对dis数组做任何操作，其结果和上图一样，队列同样不用做任何操作，它的值为：{v4}
SPFA算法手动操作过程
第五次循环此时，队首元素为v4，v4出队列，然后，对以v4为弧尾的边对应的弧头顶点进行松弛操作，可以发现v1到v6的最短路径，经过v4松弛变短了，所以更新dis数组，得到如下结果：

因为我修改了v6对应的值，而且v6也不在队列中，所以我们把v6加入队列，{v6}

第六次循环
此时，队首元素为v6，v6出队列，然后，对以v6为弧尾的边对应的弧头顶点进行松弛操作，发现v6出度为0，所以我们不用对dis数组做任何操作，其结果和上图一样，队列同样不用做任何操作。所以此时队列为空。OK，队列循环结果，此时我们也得到了v1到各个顶点的最短路径的值了，它就是dis数组各个顶点对应的值，如下图：

SPFA算法问题

即使两个图的节点和边数完全一样，仅仅是几条边的权值不同，他们的 SPFA 队列也会差距很大，如此感性上理解，SPFA 是不稳定的。
众所周知 SPFA 可以看做是 Bellman-Ford 的队列优化。 Bellman-Ford 每轮松弛会使最短路的边数至少 +1，而最短路的边数最多为 n−1，则其复杂度上界是稳定的 O(nm) 的。
但是 SPFA 能被卡，能被卡到 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 次入队。
渐进意义上，他的复杂度依然是 O(nm)，一共只有 m 条边所以每个节点最多只会入队 n 次。SPFA 在本质上只是改变的入队的顺序，其复杂度上界依然是 O(nm)，接下来介绍卡法
普通 SPFA：
链套菊花，可以让这个菊花节点反复被入队，造成时间的大量浪费。或者我们可以构造一个具有大量次短路的网格图，使得 SPFA 容易一错到底，即“在网格图中走错一次路可能导致很高的额外开销”。我们可以考虑构造一个网格图套菊花，或者把两种方法结合起来，放在同一个 Subtask 中。
渐进意义上，他的复杂度依然是 O(nm)，一共只有 m 条边所以每个节点最多只会入队 n 次。SPFA 在本质上只是改变的入队的顺序，其复杂度上界依然是 O(nm)，接下来介绍卡法
链套菊花，可以让这个菊花节点反复被入队，造成时间的大量浪费。或者我们可以构造一个具有大量次短路的网格图，使得 SPFA 容易一错到底，即“在网格图中走错一次路可能导致很高的额外开销”。我们可以考虑构造一个网格图套菊花，或者把两种方法结合起来，放在同一个 Subtask 中。
LLL 优化：
方法是比较入队的边权与 ave（平均值），如果更大则插入到队尾。卡死的方法是向 1 连接一条权值极大的边。
SLF 优化：
极其广为人知的优化，每次将入队结点距离和队首比较，如果更大则插入至队尾。依然可以用链套菊花的方式卡，“链上用几个并列在一起的小边权”。带容错的版本依然可以通过高边权和的方式卡死。
SPFA算法其它优化
除了队列优化（SPFA）之外，Bellman-Ford 还有其他形式的优化，这些优化在部分图上效果明显，但在某些特殊图上，最坏复杂度可能达到指数级。
堆优化：将队列换成堆，与 Dijkstra 的区别是允许一个点多次入队。在有负权边的图可能被卡成指数级复杂度。
栈优化：将队列换成栈（即将原来的 BFS 过程变成 DFS），在寻找负环时可能具有更高效率，但最坏时间复杂度仍然为指数级。
LLL 优化：将普通队列换成双端队列，每次将入队结点距离和队内距离平均值比较，如果更大则插入至队尾，否则插入队首。
SLF 优化：将普通队列换成双端队列，每次将入队结点距离和队首比较，如果更大则插入至队尾，否则插入队首。
D´Esopo-Pape 算法：将普通队列换成双端队列，如果一个节点之前没有入队，则将其插入队尾，否则插入队首。