SPFA算法教学

# 目录 - 引入1：单源最短路 - 原理&讲解 - 模拟&代码 - 引入2：判正(负)环 - BFS版SPFA - DFS版SPFA - 例题 - 总结 - ~~后话~~ SPFA算法是一种图论算法，可以求出单源最短路，也可检测到负环，实现起来也比较容易。但是现在很多题目会卡SPFA，所以要看情况使用。 ## 引入1：单源最短路 问：求带权有向图上一个源点到其他点的最短路径距离 如果没有非负边权，我们自然可以想到dij。但是如果有负边权呢？这时候就要用SPFA算法求解。 ## 原理&讲解 用dis数组记录源点到有向图上任意一点距离，其中源点到自身距离为0，到其他点距离为INF。将源点入队，并重复以下步骤： 1. 队首x出队 2. 遍历所有以队首为起点的有向边(x,i)，若dis[x]+w(x,i)<dis[i]，则更新dis[i] 3. 如果点i不在队列中，则i入队 4. 若队列为空，跳出循环；否则执行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出队，发现3->5使得原路不满足三角形不等式，松弛路径。由于5已在队列，直接略过。 此时队内剩下4，5，由于这两点没有出边，所以在此不枚举。 图片修改完毕 ~~手绘勿喷~~ 下面是带注释代码： (该代码为spfa+链式前向星建图) ```cpp int dis[MAXN];//dis[i]=源点s->i最短路径 bool vis[MAXN];//vis[i]表示i是否在队列 void spfa(int s){ for(int i=1;i<=MAXN;i++){//初始化 dis[i]=INF; vis[i]=true; } dis[s]=0;//源点到自身距离为0 queue <int> q;//使用C++自带队列 q.push(s);//源点入队 vis[s]=false; while(!q.empty()){//若队列不为空 int u=q.front();//取出队首元素弹出 q.pop(); vis[u]=true; for(int i=head[u];~i;i=ed[i].next){//遍历 int v=ed[i].to;// if(dis[u]+ed[i].w<dis[v]){//如果不满足三角形不等式 dis[v]=dis[u]+ed[i].w;//更新答案 if(vis[v]){//如果终点不在队列 q.push(v);//入队 vis[v]=false; } } } } } ``` ## 引入2：判正(负)环 spfa算法还可以在有向图内判正环负环，我们可以使用DFS/BFS版SPFA。注意，判负环跑最短路，判正环跑最长路。 ## BFS版SPFA BFS版SPFA判负环的思路是：当路径经过节点超过n(点数)时，图存在负环。 当我们一直绕着负环走时，由负环定义，该环边权和为负数，我们走的路径权值和是越来小的。所以当图存在负环时，最短路无解(-INF)。若一张图连通，那么它肯定是可以在经过<=n个节点从一点到任意一点的。不存在负环时，一条路径最多经过n个节点，；存在负环时，spfa就会一直绕着负环走，经过的节点一定超过n，所以只用判断最短路经过节点点数即可。代码请自行思考(因为只需作小改动)。 ## DFS版SPFA dfs版SPFA可以用来判负环，但是这个算法可以被卡到指数级。 例如判负时，我们就跑最短(改什么自己思考)。如果跑到一点时递归栈内已经有该点了，那么就是一个负环。 思路其实和bfs差不多吧，不过dfs有它自己的特点。存在负环时，最短路会一直在上面绕，我们猜测一条路径经过两次同一点即可判为存在负环。如果最短路经过两次同一点，那么肯定存在一个环。假设第二次经过同一点就往别的地方走，可以得到新路比原路(即环)路径短，这与第一次经过该点时产生矛盾(因为第一次经过该点然后走了一个环是因为该环最短)，所以肯定还是走那个环，根据BFS-SPFA中我们提到的，这张图存在负环。证毕。 代码如下： ```cpp void spfa(int a){ instack[a]=true;//节点入栈 for(int i=head[a];~i;i=Ed[i].next){//遍历出边 if(dis[a]+Ed[i].w<dis[Ed[i].to]){//如果满足条件 dis[Ed[i].to]=dis[a]+Ed[i].w;//更新答案 if(!instack[Ed[i].to]){//如果终点不在栈内 spfa(Ed[i].to);//深搜 } else{//否则 return;//有负环 } } } instack[a]=false;//将当前结点退栈 } ``` ## 例题 **拯救大兵瑞恩** ### 题面： 1944年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但是幸好麦克得到了迷宫的地形图。 　　　 迷宫的外形是一个长方形，其在南北方向被划分为N行，在东西方向被划分为M列，于是整个迷宫被划分为N*M个单元。我们用一个有序数对（单元的行号，单元的列号）来表示单元位置。南北或东西方向相邻的两个单元之间可以互通，或者存在一扇锁着的门，又或者存在一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分为P类，打开同一类的门的钥匙相同，打开不同类的门的钥匙不同。 　　　 大兵瑞恩被关押在迷宫的东南角，即（N,M）单元里，并已经昏迷。迷宫只有一个入口，在西北角，也就是说，麦克可以直接进入(1,1)单元。另外，麦克从一个单元移动到另一个相邻单元的时间为1，拿取所在单元的钥匙的时间以及用钥匙开门的时间忽略不计。 　　　 你的任务是帮助麦克以最快的方式抵达瑞恩所在单元，营救大兵瑞恩。 ### 思路： 分层建图。每一层图代表拥有钥匙的一种状态，可以用二进制的01表示然后压成十进制数。同层内，如果有墙则两单元格不联通；没有墙有门看该层拥有钥匙状态，可以开连边权为1，否则视作墙；没有墙没有门连边权1。不同层则将钥匙处按照对应状态连一条边权为0的有向边，比如第4$(100)_{2}$层的第一类钥匙处可以连向第5$(101)_{2}$的第一类钥匙处，边权为0。建完图就可以开开心心的跑spfa了。 另外加几道学SPFA的题目清单： 1. [模板：单源最短路](https://www.luogu.org/problemnew/show/P3371) 2. [模板：负环](https://www.luogu.org/problemnew/show/P3385) ## 总结 单源最短BFS，判正负环DFS~~负环模板是毒瘤题，在cz大佬的数据加强下只能用BFS了~~ 其实运用spfa难的不是在跑spfa上，因为该算法容易实现；重点是在如何建图上，如将差分约束转换为有向图等。我们应当勤思考，多刷题，把这种建图的感觉练出来。 ## 后话 鸣谢： - 管理员的辛勤审核 - 某红名神犇的指责 - 洛谷提供的好平台