算法介绍
SPFA算法是在Bellman Ford算法的基础上进行优化的，存在负权边的最短路问题和判断负环通常采用SPFA算法。Bellman Ford算法会遍历所有的边，但是有很多的边遍历了其实没有什么意义，我们只用遍历那些到源点距离变小的点所连接的边即可，只有当一个点的前驱结点更新了，该节点才会得到更新；因此考虑到这一点，我们将创建一个队列每一次加入距离被更新的结点。因此，可以发现SPFA算法其实是一个BFS的过程。
由于SPFA算法是由Bellman Ford算法优化而来，在最坏的情况下时间复杂度和它一样即时间复杂度为 O(nm)，假如题目时间允许可以直接用SPFA算法去解Dijkstra算法的题目。
最短路
注意：Bellman Ford算法可以存在负权回路，是因为其循环的次数是有限制的因此最终不会发生死循环；但是SPFA算法不可以，由于用了队列来存储，只要发生了更新就会不断的入队，因此假如有负权回路请你不要用SPFA否则会死循环。
题目链接：https://www.acwing.com/problem/content/853/
题目描述
给定一个 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 3
1 2 5
2 3 -3
1 3 4
示例输出
2
AC代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], e[N], ne[N], w[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++;
}
int spfa()
{
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (!q.empty())
{
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];
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
/* Bellman_ford算法里最后return-1的判断条件写的是dist[n]>0x3f3f3f3f/2;
* 而spfa算法写的是dist[n]==0x3f3f3f3f;
* 其原因在于Bellman_ford算法会遍历所有的边，因此不管是不是和源点连通的边它都会得到更新；
* 但是SPFA算法不一样，它相当于采用了BFS，因此遍历到的结点都是与源点连通的，因此如果你要求的* 和源点不连通，它不会得到更新，还是保持的0x3f3f3f3f。*/
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof(h));
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int res = spfa();
if (res == -1)
cout << "impossible" << endl;
else
cout << res << endl;
return 0;
}判断负环
方法：统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于n，则也说明存在环。
注意：该题是判断是否存在负环，并非判断是否存在从1开始的负环，因此需要将所有的点都加入队列中，更新周围的点。初始时将所有点插入队列中可以按如下方式理解：
在原图的基础上新建一个虚拟源点，从该点向其他所有点连一条权值为0的有向边。那么原图有负环等价于新图有负环。此时在新图上做spfa，将虚拟源点加入队列中。然后进行spfa的第一次迭代，这时会将所有点的距离更新并将所有点插入队列中。执行到这一步，就等价于视频中的做法了。那么视频中的做法可以找到负环，等价于这次spfa可以找到负环，等价于新图有负环，等价于原图有负环。
题目链接：https://www.acwing.com/problem/content/854/
题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。
输入描述
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出描述
如果图中存在负权回路，则输出 Yes，否则输出 No。
1≤n≤2000
1≤m≤10000
图中涉及边长绝对值均不超过 10000
示例输入
3 3
1 2 -1
2 3 4
3 1 -4
示例输出
Yes
AC代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
int cnt[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++;
}
bool spfa()
{
memset(dist, 0x3f, sizeof(dist));
queue<int> q;
for (int i = 1; i <= n; i++)
{
dist[i] = 0;
q.push(i);
st[i] = true;
}
while (!q.empty())
{
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()
{
cin >> n >> m;
memset(h, -1, sizeof(h));
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if (spfa())
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
