SPFA 算法是单源最短路径里面限制最小的一个算法，只要图当中没有负环就可以用 SPFA 算法，一般的最短路问题里面都一定没有负环，如果是正权图建议用迪杰斯特拉算法，如果是负权图用 SPFA 算法
SPFA 算法其实是对 Bellman-Ford 算法做一个优化，Bellman-Ford 算法每次迭代的时候，遍历所有边作更新，但是每次迭代不一定每条边都会更新，dist[b] = min(dist[b]，dist[a] + w) 不一定真的会把 dist[b] 变小，SPFA 算法就是对这个做优化，每次迭代看一下如果 dist[b] 在当前这次迭代想变小的话，一定是 dist[a] 变小了，如果 a 不变的话，b 一定不变，只有 a 变小了，b【a 的后继】才会变小
SPFA 算法就是从这一点做优化，用宽搜来做优化，迭代的时候用一个队列来做，每次第一步先把起点放到队列里面去，while(队列不为空)，队列里面存储的是所有变小的 a (只有 a 变小，b 才会变小)，只要一个节点变小了，就把它放到队列里面，用它来更新后面所有的后继
只要队列不空，也就是队列里面还有节点变小的话，第一步，先从队列里面取出队头，把队头删掉，第二步遍历 t 的所有出边，如果 t 变小的话，所有以 t 为起点的边的终点都有可能变小，更新 t 的所有出边，例如 t → b，距离是 w，如果更新成功的话，把待更新的点 b 加入队列，加入之前需要判断一下，如果队列已经有 b，b 就不用再重复加入了
基本思路就是更新过一个点，再拿这个点去更新其他点，一个点如果没有被更新过的话，那么它去更新其他点一定是没有效果的
每次把哪个点变小了，就把哪个点放到队列里面去，队列里面存储的就是待更新的点，存储方式可以选择用堆、队列. . .都可以，一般使用队列，SPFA 算法是由 Bellman-Ford 算法优化而来的，与迪杰斯特拉算法很像
SPFA 算法时间复杂度最坏是 O(nm)，一般是 O(m)
spfa 求最短路#include#include #include #include using namespace std; const int N = 100010; int n, m; //邻接表的方式存储图 int h[N], e[N], ne[N], idx; //邻接表里面需要存储一个权值 用w来表示权重 int w[N]; //距离 表示从1号点走到每个点当前的最短距离是多少 int dist[N]; //存储当前这个点是不是在队列当中 防止队列中存储重复的点 bool st[N]; //插入一条 a → b 的边 其实就是在 a 所对应的邻接表里面插入一个节点 b void add(int a, int b, int c) { //存储节点 3 的值 e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; w[idx] = c; } //spfa算法实现 int spfa() { //初始化所有点的距离 memset(dist, 0x3f, sizeof dist); dist[1] = 0; //定义一个队列存储所有待更新的点 queue q; //把1号点放到队列里面去 q.push(1); st[1] = true; //当堆不为空 while(heap.size()) { //每次取出来队头 int t = q.front(); //删除队头 q.pop(); //把st[]置为false表示这个点不在队列里面 st[t] = false; //更新t的所有邻边 for(int i = h[t]; i != -1; i = ne[i]) { //用j来表示当前这个点 int j = e[i]; //看是否能够更新这个点 if(dist[j] > dist[t] + w[i]) { //更新 dist[j] = dist[t] + w[i]; //只有j不在队列里面才把它加到队列里面去 if(!st[j]) { q.push(j); st[j] = true; } } } } if(dist[n] == ox3f3f3f) return -1; return dist[n]; } int main() { //读入点数和边数 scanf("%d%d", &n, &m); //单链表的初始化让头节点指向-1 → 如果有N个头节点让N个头节点全部指向-1 memset(h, -1, sizeof h); //读入m条边 a和b之间可能有多条边 while(m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); //读入m条边 add(a, b, n); } int t = spfa(); if(t == -1) puts("impossible"); //输出1号点到n号点的最短距离 else printf("%dn", t); return 0; }
SFPA 算法也同样可以求解迪杰斯特拉算法的题目，一般情况下，SFPA 算法比迪杰斯特拉算法更快一些，如果被卡是因为 SPFA 算法的时间复杂度最坏是 O(nm)，n 和 m 是 10w 的话，O(10w × 10 w) 等于 O()，SPFA 算法就很慢了
SPFA 算法求负环SPFA 算法与 Bellman-Ford 算法判断负环的思路是一样的，运用抽屉原理，在更新 dist 数组的时候，dist[ x ] 表示当前从 1 号点到 x 号点的最短路径的长度，与此同时记录一个 cnt 数组，dist[ x ] 表示当前 1 到 x 的最短距离，cnt 表示当前最短路边的数量，每一次更新 dist 数组的同时更新 cnt[ x ] = cnt[ t ] + 1
更新的时候意味着从 1 号点到 t 这个点，从 t 这个点再到 x 这个点的距离小于从 1 号点到 x 这个点的距离，x 这个路径的最短路就是1 ~ t 加上 t ~ x，x 经过的边数就是从 1 ~ t 的边数加上一条边就是从 1 到 x 的边数，也就是维护一个数组表示当前 1 ~ x 最短路的边数
如果在这个过程中出现 cnt[x] ≥ n，意味着从 1 到 x 经过了至少 n 条边，也就是从 1 到 x 至少经过了 n + 1 个点，由抽屉原理，一共只有 n 个点，但是路径上有 n + 1 个点，所以一定有两个点的值是相同的，假设 i 出现了两次，就意味着这个路径上是存在一个环，从 i 走到 i，路径上存在一个环不能无缘无故存在，如果不变小的话，就不会有这个环存在了。所以这个环一定是负权的，只要 cnt[x] 在这个过程当中大于等于 n，就表示我们这个图当中存在负环，以上就是 SPFA 算法判断负环的方式。总的来说就是维护一个 cnt 数组，只要在过程当中，某一次 cnt[x] ≥ n，就表示它有负环，否则就没有负环
判断负环一般用 SPFA 算法，时间复杂度最坏为 O(nm)，一般比 O(nm) 更快，Bellman-Ford 算法的时间复杂度固定为 O(nm)
spfa 判断负环题目给出 n 个点、m 条边的有向图，图当中可能存在重边和自环，边权可能为负数，判断图中是否存在负权回路。无向图是特殊的有向图，无向图当中的每条边只要建两条有向边就可以了
数据范围比较小，因为 SPFA 算法判断负环的时间复杂度其实还是蛮高的，并且只需要把 SPFA 算法稍加改动就可以了
求的不是距离的绝对值，求是否存在负环，不需要初始化
由于题目判断是不是存在负环，并不是判断是不是存在从 1 开始的负环，可能出现以下情况：图当中存在一个负环，但是从 1 号点到不了这个负环，我们只需要把所有点都放到队列里面就可以了，只要存在负环的话就一定可以找到
#includeFloyd 求最短路#include #include #include using namespace std; const int N = 100010; int n, m; //邻接表的方式存储图 int h[N], e[N], ne[N], idx; //邻接表里面需要存储一个权值 用w来表示权重 int w[N]; //距离 表示从1号点走到每个点当前的最短距离是多少 int dist[N]; //存储当前这个点是不是在队列当中 防止队列中存储重复的点 bool st[N]; //记录边数 int cnt[N]; //插入一条 a → b 的边 其实就是在 a 所对应的邻接表里面插入一个节点 b void add(int a, int b, int c) { //存储节点 3 的值 e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; w[idx] = c; } //spfa算法实现 int spfa() { //不需要初始化 求的不是距离的绝对值 求是否存在负环 //定义一个队列存储所有待更新的点 queue q; //需要把所有点全部放到队列里面 for(int i = 1; i <= n; i ++ ) { st[i] = true; q.push(i); } //当堆不为空 while(heap.size()) { //每次取出来队头 int t = q.front(); //删除队头 q.pop(); //把st[]置为false表示这个点不在队列里面了 st[t] = false; //更新t的所有邻边 for(int i = h[t]; i != -1; i = ne[i]) { //用j来表示当前这个点 int j = e[i]; //看是否能够更新这个点 if(dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; //更新cnt cnt[j] = cnt[t] + 1; //存在负环 if(cnt[j] >= n) return true; //j需要加到队列里面去 只有j不在队列里面才把它加到队列里面去 if(!st[j]) { q.push(j); st[j] = true; } } } } //不存在负环 return false; } int main() { //读入点数和边数 scanf("%d%d", &n, &m); //单链表的初始化让头节点指向-1 → 如果有N个头节点让N个头节点全部指向-1 memset(h, -1, sizeof h); //读入m条边 a和b之间可能有多条边 while(m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); //读入m条边 add(a, b, n); } if(spfa()) puts("Yes"); else puts("No"); return 0; }
Floyd 算法用来求多源汇最短路，用邻接矩阵存储图，d[i，j] 存储的是所有的边，三重循环，第一重循环 k 从 1 到 n，第二重循环 i 从 1 到 n，第三重循环 j 从 1 到 n，每次更新一遍，初始的时候，d[i，j] 存储的是所有的邻接矩阵，存储所有点之间的边
结束之后，d[i，j] 存储的就是从 i 到 j 最短路的长度，原理是基于动态规划
Floyd 算法也可以处理负权，但是不能有负权回路，如果有负权回路，最短距离会变成
Floyd 算法一共有三重循环，把邻接矩阵直接变成最短距离的矩阵，时间复杂度为 O()
部分参考
多源最短路算法 Floyd
由于图里面有重边，所以只要保留长度最小的一条边。由于题目保证了一定不存在负权回路，所以自环的边一定是正的，直接删掉就可以了
由于题目要求：1. 图中可能存在重边和自环 2. 数据保证图中不存在负权回路
所以我们需要防止自环：每个点到自身的距离为0，没有边，没有自环
如果一开始所有点都初始化无穷大memset(d，0x3f，sizeof d)，不能保证后续不存在自环
证明
图论小知识 - AcWing
从任意节点 i 到任意节点 j 的最短路径不外乎两种可能，第一种是直接从 i 到 j，第二种是从 i 经过若干个节点 k 到 j。所以，我们假设dist(i，j)为节点 u 到节点 v 的最短路径的距离，对于每一个节点k，我们检查 dist(i，k) + dist(k，j) < dist(i，j)是否成立，如果成立，说明从 i 到 k 再到 j 的路径比 i 直接到 j 的路径短，我们便设置dist(i，j) = dist(i，k) + dist(k，j)，这样一来，当我们遍历完所有节点k，dist(i，j)中记录的便是 i 到 j 的最短路径的距离。
#include#include #include using namespace std; const int N = 210, INF = 1e9; int n, m; //Q表示询问个数 题目询问了很多x到y的最短距离 并不是只求1到n的最短距离 int Q; //邻接矩阵 int d[N][N]; //算法结束后 d[a][b]表示a到b的最短距离 void floyd() { for (int k = 1; k <= n; k ++ ) for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } int main() { scanf("%d%d%d", &n, &m, &Q); //初始化邻接矩阵 for(int i = 1; i <= n; i ++ ) for(j = 1; j <= n; j ++ ) //点到自身的距离为0 到其它点的距离都为无穷大 if(i == j) d[i][j] = 0; else d[i][j] = INF; //读入每条边 while(m -- ) { int a, b, w; scanf("%d%d%d", &a, &b, &w); //如果有多条边的话只保留最小的一条边 d[a][b] = min(d[a][b], w); } //调用 Floyd 算法 floyd(); //处理所有询问 while(Q -- ) { int a, b; scanf("%d%d",&a, &b); //图里面存在负权边 如果a到b之间不存在通路的话最短距离不一定是正无穷 if(d[a][b] > INF / 2) puts("impossible"); else printf("%dn", d[a][b]); } return 0; }
