目录

引入1：单源最短路

原理&讲解

模拟&代码

引入2：判正(负)环

BFS版SPFA

DFS版SPFA

例题

总结

后话

SPFA算法是一种图论算法，可以求出单源最短路，也可检测到负环，实现起来也比较容易。但是现在很多题目会卡SPFA，所以要看情况使用。

引入1：单源最短路

问：求带权有向图上一个源点到其他点的最短路径距离

如果没有非负边权，我们自然可以想到dij。但是如果有负边权呢？这时候就要用SPFA算法求解。

原理&讲解

用dis数组记录源点到有向图上任意一点距离，其中源点到自身距离为0，到其他点距离为INF。将源点入队，并重复以下步骤：

队首x出队

遍历所有以队首为起点的有向边(x,i)，若dis[x]+w(x,i)<dis[i]，则更新dis[i]

如果点i不在队列中，则i入队

若队列为空，跳出循环；否则执行1

实际上我们可以将其理解为bfs

如果图是随机生成的，时间复杂度为 O(KM) （K可以认为是个常数，m为边数，n为点数）

但是实际上SPFA的算法复杂度是 O(NM) ，可以构造出卡SPFA的数据，让SPFA超时。

在NOI 2018的第一天第一题中，出题人卡了SPFA算法，导致100分变成60分，所以在没有负环、单纯求最短路径，不建议使用SPFA算法，而是用Dijkstra算法。

在初一我们学到一条三角形中的性质，即同一三角形内两边之和大于第三边。而最短路中如u->v的最短路它是小于等于其它任意路径的，这使我们容易yy到三角形。也就是说，我们实际上每次都是在判断这条路径符不符合三角形不等式，若不符合，我们就将原先的路径松弛为现在的路径，使得现在的路径满足三角形不等式。但是为什么松弛后要将终点入队呢？SPFA的过程是BFS，它是不停扩展节点的。而当我们更新了这一条路径，那么可能会出现基于这一条路径的新路，我们需要判断原路与新路是否满足三角形不等式。

模拟&代码

我们可以手推这张图模拟一下~

我们以1为源点，初始化：dis[源点]=0，其他为正无穷，并将源点入队。

队首1出队，并枚举它的出边1->2,1->3。由dis[1]+w(1,2)=1<dis[2]=INF,dis[1]+w(1,3)=6<dis[3]=INF得dis[2]=dis[1]+w(1,2)=1,dis[3]=dis[1]+w(1,3)=6，并将2，3入队。

队首2出队，枚举它的出边2->3,2->4,2->5。都不满足三角形不等式，所以松弛它们。并将3，4，5入队，但由于3已在队内，所以不管。

队首3出队，没有能松弛的边，直接略过。

此时队内剩下4，5，由于这两点没有出边，所以在此不枚举。

手绘勿喷

下面是带注释代码：

(该代码为spfa+链式前向星建图)

引入2：判正(负)环

spfa算法还可以在有向图内判正环负环，我们可以使用DFS/BFS版SPFA。注意，判负环跑最短路，判正环跑最长路。

BFS版SPFA

BFS版SPFA判负环的思路是：当路径经过节点超过n(点数)时，图存在负环。

当我们一直绕着负环走时，由负环定义，该环边权和为负数，我们走的路径权值和是越来小的。所以当图存在负环时，最短路无解(-INF)。若一张图连通，那么它肯定是可以在经过<=n个节点从一点到任意一点的。不存在负环时，一条路径最多经过n个节点；存在负环时，spfa就会一直绕着负环走，经过的节点一定超过n，所以只用判断最短路经过节点点数即可。代码请自行思考(因为只需作小改动)。

DFS版SPFA

dfs版SPFA可以用来判负环。

例如判负时，我们就跑最短(改什么自己思考)。如果跑到一点时递归栈内已经有该点了，那么就是一个负环。

思路其实和bfs差不多吧，不过dfs有它自己的特点。存在负环时，最短路会一直在上面绕，我们猜测一条路径经过两次同一点即可判为存在负环。如果最短路经过两次同一点，那么肯定存在一个环。假设第二次经过同一点就往别的地方走，可以得到新路比原路(即环)路径短，这与第一次经过该点时产生矛盾(因为第一次经过该点然后走了一个环是因为该环最短)，所以肯定还是走那个环，根据BFS-SPFA中我们提到的，这张图存在负环。证毕。

代码如下：

例题：拯救大兵瑞恩

题面：

1944年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但是幸好麦克得到了迷宫的地形图。

迷宫的外形是一个长方形，其在南北方向被划分为N行，在东西方向被划分为M列，于是整个迷宫被划分为N*M个单元。我们用一个有序数对（单元的行号，单元的列号）来表示单元位置。南北或东西方向相邻的两个单元之间可以互通，或者存在一扇锁着的门，又或者存在一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分为P类，打开同一类的门的钥匙相同，打开不同类的门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角，即（N,M）单元里，并已经昏迷。迷宫只有一个入口，在西北角，也就是说，麦克可以直接进入(1,1)单元。另外，麦克从一个单元移动到另一个相邻单元的时间为1，拿取所在单元的钥匙的时间以及用钥匙开门的时间忽略不计。

你的任务是帮助麦克以最快的方式抵达瑞恩所在单元，营救大兵瑞恩。

思路：

分层建图。每一层图代表拥有钥匙的一种状态，可以用二进制的01表示然后压成十进制数。同层内，如果有墙则两单元格不联通；没有墙有门看该层拥有钥匙状态，可以开连边权为1，否则视作墙；没有墙没有门连边权1。不同层则将钥匙处按照对应状态连一条边权为0的有向边，比如第4 (二进制100) 层的第一类钥匙处可以连向第5 (二进制101) 的第一类钥匙处，边权为0。建完图就可以开开心心的跑spfa了。

另外加几道学SPFA的题目清单（SPFA过不了P4779 模板：单源最短路径-标准版）：

模板：单源最短路

模板：负环

总结

单源最短BFS，判正负环DFS负环模板是毒瘤题，在cz大佬的数据加强下只能用BFS了

其实运用spfa难的不是在跑spfa上，因为该算法容易实现；重点是在如何建图上，如将差分约束转换为有向图等。我们应当勤思考，多刷题，把这种建图的感觉练出来。

后话

鸣谢：

管理员的辛勤审核

某红名神犇的指责

洛谷提供的好平台

本文发布于洛谷日报，特约作者：Ryan_wxn_

原文地址：