2019.10.11 Upd:这是 ZS 时期写的一篇非常 naive 的博客,别看了。
SPFA 会被卡,Dij 才最好。


SPFA真是最好的单源最短路算法,没有之一。

SPFA全称是Shortest Path Faster Algorithm,直译过来就是“最短路更快算法”,从这个名称就能看出SPFA效率很高。SPFA加上SLF优化以后被称作单源最短路的“无敌”,时间复杂度可以达到O(ke)(k表示平均每个节点入队次数,k≤2,e表示边数),可以刷负边权。

SPFA需要使用邻接表这种存图方式(也可以说邻接表是一种空间优化,因为其实用普通的二维矩阵存图也可以),故要理解SPFA首先要理解邻接表。

邻接表

邻接表是个黑科技的玩意儿:用来存图,是一条边一条边存的,有多少边就存多少。对于每条边,只需要关注关于这条边的几个值,也就是我们建立的几个数组(假设这条边是i):
son[i]:这条边的儿子。我们把所有图都理解为有向图(如果是无向图就x到y建边,再y到x建边)。
lnk[x]:x这个点连出的最后一条边(我们假设与x连接的边都是有顺序的。这个顺序任意,就是我们添边的顺序)。
nxt[i]:按刚刚的顺序,i这条边的父节点连出的下一条边。
w[i]:编号为i的边的权值。

设要将点x,y连通,连通后边的权值为z,如果目前已经有tot条边,那么这条边就极为tot+1,直接tot++即可。那么y就是tot这条边的儿子,即son[tot]=y;权值为z,则w[tot]=z;最后x点连接的是tot,lnk[x]表示x连出的边,故lnk[x]=tot;但是这样就把上一条边清掉了,所以在lnk[x]=tot之前应该nxt[tot]=lnk[x]。

SPFA

接下来就是SPFA主程序了。

先解释下这些数组都是啥:
dst[x]:表示由起点到x点的最短路(就是存最终的结果,不断修正)。
vis[x]:(布尔类型)标记x点是否在队列中
que[x]:就是BFS里的队列,对应有head和tail。

SPFA用于刷单源最短路。DP+BFS的思想,其实工作原理和BFS差不多:先把这些点一个个入队,再拓展下去,同时修正dst数组。在把head++拓展的同时,把vis[que[head]]打成false了,为什么要这么做?引用一段FQY大佬「深度解析SPFA的原理与构造」里的一段话:

我们先看head往前走了一个点后,把vis标记打掉了。为什么要把已入队的标记去掉呢?我们知道,在有边权的图中,路径短的路线距离不一定短(即走过的点少的路线dist不一定就小)那么因为广搜的特性(广度优先,即路径短优先)导致先修正dist的值(先修正的路线路径一定短)不一定是最后的答案,有可能后面还会再次扩展到当前的head点,而修正出的dist值较小(后修正的路线路径较长而距离可能小)。在这样一种情况下,为了后面路径长的路线也能修正到该点,就把这里的标记去掉了。

也就是说这里的vis[que[head]]标成假值,是为了之后que[head]这个点可能重新入队考虑的。为什么要重新入队?因为之后可能还重复修正到que[head]并且修正得到的是更优秀的解(上面一段文字解决了这个疑惑:那么为什么又会重新修正到这个点,得出更优秀的解?广度优先搜索不是路径短的优先,先修正的更优秀吗?不,因为有边权,路径短的不一定dst小,所以有的点要重复修正)。

接下来由que[head]开始拓展,一旦发现新的路线(dst[que[head]]+w[i])比原来的(dst[son[i]])优秀就修正,如果vis[son[i]]==false,也就是说son[i]不在队列中,当然就是入队了,但是如果son[i]在队列中,要不要入队呢?显然不需要。但是如果入队了也不会影响答案。为什么不需要入队呢?(可能你的疑问是:在修正后面这个son[i]的时候,可能会更优秀啊?)因为如果son[i]已经在队列中,那么说明以后一定会再从son[i]开始修正,那么问题就是从上一个son[i]之后到这个son[i]之前这一段,会不会导致后面能修正出更优秀的son[i]?显然这不需要考虑,因为如果更优秀,之后还是会重新把son[i]修正/入队的!所以,这个时候son[i]就不要入队,因为入队无疑会浪费时间和空间。

SLF优化

既然SPFA由BFS而来,那么我们可以看看两者有什么区别:BFS解的题目为什么元素不需要多次入队?就是因为保证了序列的单调递增,或者说边权相等。比如说一些一格一格走的走迷宫题目,边权都是1,就能确保序列的单调递增。也就是因为SPFA的序列不是单调的,所以效率不如BFS(因为每个节点要多次入队)。那么我们就可以思考:能不能让SPFA效率接近BFS?那么自然想到如果能让SPFA的序列尽量单调递增该多好。很容易想到这个优化:如果当前入队的点(que[tail])比下一个要走的点(que[head+1])距离小就交换这两个点。因为对于队列里的每个点,先刷后刷并不会影响答案。

从原理来看,为什么SLF优化真的能起到优化的作用呢?当我们把tail放到前面了以后,由于dst[que[tail]]比较小,所以先修正出的后面一系列值都离最优解比较近,比原来的dst[que[head+1]]修正出的更优。那么在之后做的时候就会少修正几次,达到时间优化的目的。

题外话

维基百科条目:
https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm
(中文的直接重定向到了https://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%9B%BC-%E7%A6%8F%E7%89%B9%E7%AE%97%E6%B3%95
上面说:

In China, an algorithm which adds a first-in first-out queue to the Bellman-Ford algorithm, known as SPFA, published by Fanding Duan in 1994, is popular with students who take part in NOIP and ACM-ICPC.

在中国,由Fanding Duan(段凡丁)于1994年出版的一种在Bellman-Ford算法(称为SPFA)中增加先进先出队列的算法,受到参加NOIP和ACM-ICPC的学生的欢迎。

据说SPFA还是西南交通大学软件学院副院长段凡丁于1994年提出的。不过据说论文里证明时间复杂度的部分是错的,所以国际上不承认SPFA算法,只承认Bellman-Ford的队列优化。

 

SPFA算法真是太太太太太有用了!!!

参考:
WM的《SPFA算法总结》
FQY大佬的《深度解析SPFA的原理与构造》