1、SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法，它是Bellman-ford的队列优化，它是一种十分高效的最短路算法。 2、很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。 3、但是，SPFA算法稳定性较差，在稠密图中SPFA算法时间复杂度会退化。 4、SPFA算法还可以判断图中是否有负权环，即一个点入队次数超过N。
1、建立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0） 2、执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。 3、重复执行直到队列为空。
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
int n; // 总点数 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数 bool st[N]; // 存储每个点是否在队列中 // 如果存在负环，则返回true，否则返回false。 bool spfa() { // 不需要初始化dist数组 // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。 queue<int> q; for (int i = 1; i <= n; i ++ ) { q.push(i); st[i] = 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]; cnt[j] = cnt[t] + 1; if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环 if (!st[j]) { q.push(j); st[j] = true; } } } } return false; } 作者：yxc 链接：https://www.acwing.com/blog/content/405/ 来源：AcWing四、经典例题 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 3 1 2 5 2 3 -3 1 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 ++ ; } int spfa() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; queue<int> q; q.push(1); st[1] = true; while (q.size()) { int t = q.front(); q.pop(); st[t] = false;//从队列中取出来之后该节点st被标记为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]; } 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); } int t = spfa(); if (t == 0x3f3f3f3f) puts("impossible"); else printf("%d\n", t); return 0; }AcWing 852. spfa判断负环 给定一个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注意 需要从每个点都出发一次，才能完全确定此图中是否有环
cnt[j]=n 编号编号为j的节点是第n个加入路径的节点，
负环：环路之和为负， 求最短路的时候会不断在负环路打转。
#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;//dist 存的是当前从1号点到n号点的长度； 邻接表就是数组模拟链表，图中每个节点拉出一条链，存储其所有邻边，e[i]表示邻边的另一个端点，w[i]表示邻边长度，ne[i]表示链表的下一个节点下标，idx表示当前用到第几个下标 int dist[N], cnt[N];//cnt数组表示到达当前这个点最短路的边数 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() { 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])//如果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; }