SPFA 算法总结

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首先要理解邻接表。

邻接表

设要将点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

先解释下这些数组都是啥： 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值较小（后修正的路线路径较长而距离可能小）。在这样一种情况下，为了后面路径长的路线也能修正到该点，就把这里的标记去掉了。

接下来由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优化

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

题外话

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算法真是太太太太太有用了！！！

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