?前言
前面，我们分别介绍了Dijkstra算法（【最短路算法】一篇文章彻底弄懂Dijkstra算法|多图解+代码详解）和Bellman-Ford算法
【最短路算法】第二弹：一文弄懂Bellman-Ford(贝尔曼福特算法)
前者用于求单源、正权边最短路问题，后者用于求单源、带负权边最短路问题。通过对Bellman-Ford算法讲解，我们知道，Bellman-Ford算法美中不足的一点在于时间复杂度是O(nm)，时间复杂度过高。
今天，我们学习的spfa算法，优化了Bellman-Ford算法，时间复杂度 平均情况下 O(m)，最坏情况下 O(nm), n 表示点数，m 表示边数。
目录
?前言?一、算法思想?二、spfa求最短路?三、spfa判断负权回路
?一、算法思想
在讲具体算法思想之前，我们来仔细探讨一下，优化的点在哪里？
Bellman-ford算法慢，就慢在，其实在后面遍历时，每次迭代都要遍历所有边。前面我们说到过，迭代次数代表从源点出发，经过不超过迭代次数的边数，所经过的顶点的dist都是准确的，确定的。但是在后面迭代中，又重复去遍历这些边，其实是没有必要的。
因为判断一个点的松驰条件为:假设边为a→bdist[b] = min (dist[b], dist[a]+w),当dist[a]（a其实不是某一个点，代表的是从a指向b的边的一群顶点）都一直没有更新，dist[b]当然也不会更新，确定好了dist[b]，在后面遍历中，dist[b] = min (dist[b], dist[a]+w)完全没有必要进行。那如何减少这一无意义操作呢？
核心就是，我们只对其dist有更新的顶点进行松驰！（注意，这样一来，spfa当然就不会有bellman-Ford算法的那种迭代次数的意义存在！）
spfa，利用宽搜思想，使用队列为数据结构，优化了这一点。，优化了这一点。
?首先，将dist变小的即有被更新的点入队（因为它的更新，一般会带来其他点的更新）
?取出队列元素，并将其弹出
?对该元素的出边元素进行遍历&松驰
?如果有元素松驰成功（dist更新，也就是变小了），那么该元素也入队
算法模板如下：（from acWing)
int n; // 总点数int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边int dist[N]; // 存储每个点到1号点的最短距离bool st[N]; // 存储每个点是否在队列中// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1int spfa(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0; queue<int> q; q.push(1); st[1] = true; while (q.size()) { auto t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入 { q.push(j); st[j] = true; } } } } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n];}?二、spfa求最短路
acWing 851. spfa求最短路
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 impossible。
数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。
输入样例：
3 31 2 52 3 -31 3 4输出样例：
2#include <cstring>#include <iostream>#include <algorithm>#include <queue>using namespace std;const int N = 100010;int n,m;int h[N],w[N],e[N],ne[N],idx;//邻接表存储图int dist[N];bool st[N];//标记节点是否在队列中//构建边void add(int a,int b, int c){ e[idx] = b,w[idx] = c, ne[idx] = h[a],h[a] = idx++;}void spfa(){ memset(dist, 0x3f, sizeof(dist)); dist[1] = 0; queue<int> q;//队列 q.push(1);//因为dist[1] 从0x3f3f3f3f松驰为了0，加入队列 st[1] = true; while(q.size()){//while队列不空 int t = q.front();//取出队头元素，由该点更新其出边点 q.pop();//出队 st[t] = false; //遍历t点的出边点 for(int i = h[t]; i!=-1; i = ne[i]){ int j = e[i]; //判断该点是否可以进行松驰操作并松驰 if(dist[j] > dist[t] + w[i]){ dist[j] = dist[t] +w[i]; if(!st[j]){//对该点做了更新，把该点也要入队 q.push(j); st[j] = true; } } } }}int main(){ scanf("%d%d",&n,&m); //！h[N]数组要先初始化 memset(h,-1,sizeof(h)); for(int i = 0; i < m; i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } spfa(); if(dist[n] == 0x3f3f3f3f) puts("impossible"); else printf("%d\n",dist[n]); return 0;}?三、spfa判断负权回路
spfa判断负环给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
如果图中存在负权回路，则输出 Yes，否则输出 No。
数据范围
1≤n≤2000, 1≤m≤10000, 图中涉及边长绝对值均不超过 10000。
?思路
统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于n，则也说明存在负环
1、dist[x] 记录虚拟源点到x的最短距离
2、cnt[x] 记录当前x点到虚拟源点最短路的边数，初始每个点到虚拟源点的距离为0，只要他能再走n步，即cnt[x] >= n，则表示该图中一定存在负环，由于从虚拟源点到x至少经过n条边时，则说明图中至少有n + 1个点，表示一定有点是重复使用
3、若dist[j] > dist[t] + w[i],则表示从t点走到j点能够让权值变少，因此进行对该点j进行更新，并且对应cnt[j] = cnt[t] + 1,往前走一步
?详细注释题解
#include <cstring>#include <iostream>#include <algorithm>#include <queue>using namespace std;const int N = 2010, M = 10010;int n,m;int h[N],w[M],e[M],ne[M],idx;int dist[N],cnt[N];bool st[N];void add(int a,int b,int c){ e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++; }//spfa算法判断负权回路bool spfa(){ queue<int> q; //将所有顶点都入队 for(int i = 1; i <= n; i ++){ st[i] = true; q.push(i); } while(q.size()){ int t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if (cnt[j] >= n) return true; if (!st[j]) { q.push(j); st[j] = true; } } } } return false;}int main(){ scanf("%d%d",&n,&m); memset(h,-1,sizeof(h)); while(m --){ int a, b, c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } if(spfa()) puts("Yes"); else puts("No"); return 0;}?注意点
为什么不用初始化dist[N]? 因为负环的存在，所以即使每个点距离虚拟原点距离为0，负权回路的存在就可以更新某个点的dist为更小的值.这题是判断，只要有这个变小（松驰）趋势就Ok，并不是求最短路注意：该题是判断是否存在负环，并非判断是否存在从1开始的负环，因此需要将所有的点都加入队列中，更新周围的点.换句话来说，**从哪个点出发并不重要，重要的是是否有负环！**一定要将所有点入队我认为是因为图可能会不连通，如果负环是在和1这个点不连通的部分（可能图中存在负环，但是从一号点到不了），就无法查到，所以要将所有点都入队！遍历所有点，肯定能遍历到有负环的回路，只要有负环,dist就会更新，顶点就会接着入队，cnt也接着增加！对比：以 S 点为源点跑 Bellman-Ford 算法时，如果没有给出存在负环的结果，只能说明从 S 点出发不能抵达一个负环，而不能说明图上不存在负环。
LeetCode每日一题–进击大厂算法