Acwing - 算法基础课 - 笔记（八） 今天药忘吃喽~ 2022-10-10 11:26 158阅读 0赞 ### 文章目录 ### * * 搜索与图论（二） * * 单源最短路 * 多源汇最短路 * 算法思路 * * 朴素Dijkstra * 堆优化版Dijkstra * Bellman-Ford * SPFA * Floyd * 总结 ## 搜索与图论（二） ## 这一节讲的是最短路。 常见的最短路问题，一般分为两大类： * **单源最短路** * **多源汇最短路** 在最短路问题中，**源点**也就是**起点**，**汇点**也就是**终点**。 ### 单源最短路 ### **单源最短路**，指的是求**一个点**，到其他所有点的最短距离。（**起点是固定的，单一的**） 根据是否存在权重为负数的边，又分为两种情况 * **所有边的权重都是正数** 通常有两种算法 * **朴素Dijkstra** 时间复杂度O(n2)，其中n是图中点的个数，m是边的个数 * **堆优化版的Dijkstra** 时间复杂度O(mlogn) 两者孰优孰劣，取决于图的疏密程度（取决于点数n，与边数m的大小关系）。当是稀疏图（n和m是同一级别）时，可能**堆优化版的Dijkstra**会好一些。当是稠密图时（m和n2是同一级别），使用**朴素Dijkstra**会好一些。 * **存在权重为负数的边** 通常有两种算法 * **Bellman-Ford** 时间复杂度O(nm) * **SPFA** 时间复杂度一般是O(m)，最差O(nm)，是前者的优化版，但有的情况无法使用SPFA，只能使用前者，比如要求最短路不超过k条边，此时只能用Bellman-Ford ### 多源汇最短路 ### 求多个起点到其他点的最短路。（**起点不是固定的，而是多个**） **Floyd算法**（时间复杂度O(n3)） ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70][] 最短路问题的核心在于，把问题抽象成一个最短路问题，并**建图**。图论相关的问题，**不侧重于算法原理，而侧重于对问题的抽象**。 Dijkstra基于贪心，Floyd基于动态规划，Bellman-Ford基于离散数学。 算法的选用：通常来说，单源最短路的，如果没有负权重的边，用Dijkstra，有负权重边的，通常用SPFA，极少数用Bellman-Ford；多源最短路的，用Floyd。 ### 算法思路 ### #### 朴素Dijkstra #### 假设图中一共有n个点，下标为1~n。下面所说的**某个点的距离**，都是指该点到起点（1号点）的距离。 算法步骤如下，用一个集合`s`来存放**最短距离已经确定**的点。 1. **初始化距离**，`d[1] = 0， d[i] = +∞`。即，将起点的距离初始化为0，而其余点的距离当前未确定，用正无穷表示。 2. 循环 每次从**距离已知**的点中，**选取一个不在`s`集合中，且距离最短的点**（这一步可以用小根堆来优化），遍历该点的所有出边，更新这些出边所连接的点的距离。并把该次选取的点加入到集合`s`中，因为该点的最短距离此时已经确定。 3. 当所有点都都被加入到`s`中，表示全部点的最短距离都已经确定完毕 注意某个点的**距离已知**，并不代表此时**这个点的距离**就是最终的最短距离。在后续的循环中，可能用一条更短距离的路径，去更新。 练习题：[acwing - 849: Dijkstra求最短路 I ][acwing - 849_ Dijkstra_ I] 题解（C++） #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 510; const int INF = 0x3f3f3f3f; // 正无穷 int g[N][N]; // 稠密图采用邻接矩阵存储 int d[N]; // 距离 int n, m; bool visited[N]; int dijkstra() { d[1] = 0; // 每次 for(int i = 1; i <= n; i++) { //找到一个距起点距离最小的点 int t = 0; // d[0]未被使用, 其值一直是 INF for(int j = 1; j <= n; j++) { if(!visited[j] && d[j] < d[t]) { t = j; } } if(t == 0) break; // 未找到一个点, 提前break // 找到该点 visited[t] = true; // 放入集合s // 更新其他所有点的距离 for(int i = 1; i <= n; i++) { d[i] = min(d[i], d[t] + g[t][i]); } } if(d[n] == INF) return -1; else return d[n]; } int main() { // 初始化 memset(d, 0x3f, sizeof d); memset(g, 0x3f, sizeof g); scanf("%d%d", &n, &m); while(m--) { int x, y, z; scanf("%d%d%d", &x, &y, &z); g[x][y] = min(g[x][y], z); // 重复边只需要保留一个权重最小的即可 } printf("%d", dijkstra()); return 0; } 题解（Java） import java.util.Arrays; import java.util.Scanner; /** * @Author yogurtzzz * @Date 2021/6/25 9:01 * * 稠密图, 使用邻接矩阵存储 **/ public class Main { static final int INF = 0x3f3f3f3f; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n, m; n = scanner.nextInt(); m = scanner.nextInt(); int[][] g = new int[n + 1][n + 1]; // 图的邻接矩阵存储 for(int i = 0; i < n + 1; i++) { for (int j = 0; j < n + 1; j++) g[i][j] = INF; // 初始化全部距离为正无穷 } while(m-- > 0) { int x, y, z; x = scanner.nextInt(); y = scanner.nextInt(); z = scanner.nextInt(); g[x][y] = Math.min(g[x][y], z); // 解决重边, 保留最小距离的边即可 } System.out.println(dijkstra(g, n)); } /** * @param g 图的邻接矩阵表示 * @param n 图中点的个数 * **/ static int dijkstra(int[][] g, int n) { int[] distance = new int[n + 1]; boolean[] visited = new boolean[n + 1]; //状态变量 Arrays.fill(distance, INF); // 初始化距离为正无穷 distance[1] = 0; // 起点的距离为0 // 循环n次 for (int i = 0; i < n; i++) { // 先找出距离最小的点 int min = 0; for(int j = 1; j <= n; j++) { if (!visited[j] && distance[j] < distance[min]) { min = j; } } if (min == 0) break; // 所有点都遍历结束 // 找到了距离最小的点 visited[min] = true; // 这里是为了解决自环 // 更新距离, 枚举所有列 for(int j = 1; j <= n; j++) { // 当存在一个出边时, 更新其距离 if (g[min][j] != INF) distance[j] = Math.min(distance[j], distance[min] + g[min][j]); } } if (distance[n] == INF) return -1; else return distance[n]; } } #### 堆优化版Dijkstra #### 堆可以自己手写（用数组模拟），也可以使用现成的（C++的STL提供了priority\_queue，Java的JDK中提供了PriorityQueue） 练习题：[acwing - 850: Dijkstra求最短路 II ][acwing - 850_ Dijkstra_ II] 题解：手写堆（C++） #include<iostream> #include<cstring> #include<algorithm> using namespace std; // 稀疏图, 用邻接表来存储, 并且选用堆优化的Dijkstra const int N = 2e5; const int INF = 0x3f3f3f3f; // 正无穷 int h[N], e[N], w[N], ne[N], idx; // 邻接表存储, -1表示空节点 int d[N]; // 距离 bool visited[N]; // 状态 int n, m; int hVal[N], hDis[N], hSize; // 数组模拟堆, hVal存节点编号, hDis存节点距离 int ph[N], hp[N]; // 记录堆中节点下标和图中节点编号的映射关系 // 交换2个下标, 下标是堆中的下标 void heap_swap(int a, int b) { swap(hp[a], hp[b]); swap(ph[hp[a]], ph[hp[b]]); swap(hVal[a], hVal[b]); swap(hDis[a], hDis[b]); } // 向上调整, 记得是根据距离hDis来调整 void up(int pos) { while(pos / 2 >= 1 && hDis[pos / 2] > hDis[pos]) { heap_swap(pos, pos / 2); pos /= 2; // 少写了这一行, 找了1小时！ } } // 向下调整, 记得是根据距离hDis来调整 void down(int pos) { int min = pos; if(2 * pos <= hSize && hDis[2 * pos] < hDis[min]) min = 2 * pos; if(2 * pos + 1 <= hSize && hDis[2 * pos + 1] < hDis[min]) min = 2 * pos + 1; if(min != pos) { heap_swap(pos, min); down(min); } } // 获取并弹出堆顶节点 int pop() { if(hSize == 0) return 0; // 堆为空 int res = hVal[1]; // 节点编号 heap_swap(1, hSize); // 交换堆顶和堆尾 hSize--; // down(1); // 调整堆 return res; } // 插入一个节点到堆, x是节点编号, dis是该节点到起点的距离 void insert_to_heap(int x, int dis) { // 下标从1开始 hSize++; ph[x] = hSize; hp[hSize] = x; // 插入一个数到堆 hVal[hSize] = x; // 记录节点编号 hDis[hSize] = dis; // 记录节点距离 up(hSize); // 向上调整 } // 在x和y之间连一条边, 权重是z void add(int x, int y, int z) { // 记录该条边到邻接表 e[idx] = y; w[idx] = z; ne[idx] = h[x]; h[x] = idx++; } int dijkstra() { d[1] = 0; // 初始化, 起点(1号点)距离为0 insert_to_heap(1, 0); // 将起点插入堆 for(int i = 1; i <= n; i++) { // 每次确定一个节点 int t = pop(); // 获取当前距离最短的点, 节点编号为1~n if(t == 0) break; // 堆中没有元素, 表明节点已全部访问过, 提前结束 if(visited[t]) continue; // 该点已经在集合s中, 直接跳过 visited[t] = true; // 更新所有出边的点的距离 for(int j = h[t]; j != -1; j = ne[j]) { int u = e[j]; // 节点编号 int du = w[j]; // 边长 if(d[u] > d[t] + w[j]) { d[u] = d[t] + w[j]; insert_to_heap(u, d[u]); // 重复的点也可以直接插入, 没有关系 } } } if(d[n] == INF) return -1; else return d[n]; } int main() { memset(h, -1, sizeof h); // 初始化 memset(d, 0x3f, sizeof d); // 距离初始化为INF memset(hVal, 0, sizeof hVal); memset(hDis, 0, sizeof hDis); scanf("%d%d", &n, &m); while(m--) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, z); } printf("%d", dijkstra()); return 0; } 题解：使用现成的堆（Java） import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; /** * @Author yogurtzzz * @Date 2021/6/25 9:33 * * 堆优化版的 Dijkstra * 稀疏图, 用邻接链表来存 **/ public class Main { static class Pair { int first; int second; Pair(int first, int second) { this.first = first; this.second = second; } } static Scanner scanner = new Scanner(System.in); static int INF = 0x3f3f3f3f; static final int N = 200000; static int[] h; static int[] e = new int[N], w = new int[N], ne = new int[N];// 图的邻接表表示, 数组模拟链表 static int idx; // 用来分配链表节点 public static void main(String[] args) { int n = readInt(), m = readInt(); h = new int[n + 1]; Arrays.fill(h, -1); // 初始化, 全部邻接表都是-1, 表示空链表 while(m-- > 0) { int x = readInt(), y = readInt(), z = readInt(); add(x, y, z); } System.out.println(dijkstra(n)); } private static int dijkstra(int n) { int[] distance = new int[n + 1]; boolean[] visited = new boolean[n + 1]; Arrays.fill(distance, INF); distance[1] = 0; // 初始化起点距离 // 小根堆 PriorityQueue<Pair> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o.first)); heap.offer(new Pair(0, 1)); // 插入起点到堆中, first是距离, second是节点编号 for(int i = 0; i < n; i++) { Pair p = heap.poll(); // 获取当前距离最小的节点 if (p == null) break; // 堆里没有元素了, 提前结束 int nodeNo = p.second, nodeDis = p.first; // 获取该节点的编号和距离 visited[nodeNo] = true; // 解决自环 for(int j = h[nodeNo]; j != -1; j = ne[j]) { // 从邻接表中获取该节点的所有出边, 依次更新 int nextNodeNo = e[j]; int nextNodeWeight = w[j]; if (distance[nextNodeNo] > nodeDis + nextNodeWeight) { // 更新 distance[nextNodeNo] = nodeDis + nextNodeWeight; // 插入到堆中 heap.offer(new Pair(distance[nextNodeNo], nextNodeNo)); } } } return distance[n] == INF ? -1 : distance[n]; } // 添加一条边 private static void add(int x, int y, int z) { e[idx] = y; w[idx] = z; ne[idx] = h[x]; h[x] = idx++; } private static int readInt() { return scanner.nextInt(); } } #### Bellman-Ford #### 算法思路 > 循环n次 > > 每次循环，遍历图中所有的边。对每条边`(a, b, w)`，（指的是从a点到b点，权重是w的一条边）更新`d[b] = min(d[b], d[a] + w)` （可以定义一个类，或者C++里面的结构体，存储a，b，w。表示存在一条边a点指向b点，权重为w）。则遍历所有边时，只要遍历全部的结构体数组即可 循环的次数的含义：假设循环了k次，则表示，从起点，经过不超过k条边，走到每个点的最短距离。 该算法能够保证，在循环n次后，对所有的边`(a, b, w)`，都满足`d[b] <= d[a] + w`。这个不等式被称为**三角不等式**。上面的更新操作称为**松弛操作**。 该算法适用于有负权边的情况。 **注意：如果有负权回路的话，最短路就不一定存在了。**（注意是不一定存在）。当这个负权回路处于1号点到n号点的路径上，则每沿负权回路走一圈，距离都会减少，则可以无限走下去，1到n的距离就变得无限小（负无穷），此时1号点到n号点的最短距离就不存在。而如果负权回路不在1号点到n号点的路径上，则1到n的最短距离仍然存在。 该算法可以求出来，图中是否存在负权回路。如果迭代到第n次，还会进行更新，则说明存在一条最短路，路径上有n条边，n条边则需要n + 1个点，而由于图中一共只有n个点，所以这n + 1个点中一定有2个点是同一个点，则说明这条路径上有环；有环，并且此次进行了更新，说明这个环的权重是负的（只有更新后总的距离变得更小，才会执行更新）。 但求解负权回路，通常用SPFA算法，而不用Bellman-Ford算法，因为前者的时间复杂度更低。 由于循环了n次，每次遍历所有边（m条边）。故Bellman-Ford算法的时间复杂度是O(n×m)。 练习题：[acwing - 853: 有边数限制的最短路][acwing - 853_] #include<iostream> #include<cstring> using namespace std; const int N = 510, M = 10010; const int INF = 0x3f3f3f3f; struct Edge { int a, b, w; } edge[M]; // 直接用结构体来存储全部边 int n, m, k, d[N], tmp[N]; void bellman_ford() { memset(d, 0x3f, sizeof d); d[1] = 0; // 初始化 for(int i = 0; i < k; i++) { memcpy(tmp, d, sizeof d); // 需要备份 for(int j = 0; j < m; j++) { Edge e = edge[j]; int a = e.a, b = e.b, w = e.w; if(tmp[a] == INF) continue; if(d[b] > tmp[a] + w) { // 用备份的tmp来进行计算, 以防出现串联更新的情况 // 串联更新虽然不影响最终的最短距离, 但会影响[经过不超过k条边的最短距离]这个语义 // 比如在外层循环进行了2次时, 此时应当找到了从起点到其他点,经过不超过2条边的最短距离 // 而如果串联更新的话, 可能在这第2次循环时, 已经更新了多次, 得到的最短距离是经过了3条边的最短距离 // 另外, 上面的if中应该用 d[b] > tmp[a] + w // 而不应当用 tmp[b] > tmp[a] + w // 当a和b之间存在重边时, 若使用后者作为条件, 则无法取到a,b之间权重最小的那条边 // 更新 d[b] = tmp[a] + w; } } } if(d[n] == INF) printf("impossible"); else printf("%d", d[n]); } int main() { scanf("%d%d%d", &n, &m, &k); for(int i = 0; i < m; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); edge[i] = { x, y, z}; } bellman_ford(); return 0; } #### SPFA #### 若要使用SPFA算法，一定要求图中不能有负权回路。只要图中没有负权回路，都可以用SPFA，这个算法的限制是比较小的。 SPFA其实是对Bellman-Ford的一种优化。 它优化的是这一步：`d[b] = min(d[b], d[a] + w)` 我们观察可以发现，只有当`d[a]`变小了，才会在下一轮循环中更新`d[b]` 考虑用BFS来做优化。用一个队列queue，来存放距离变小的节点。 （和Dijkstra很像） 练习题：[acwing - 851: spfa求最短路][acwing - 851_ spfa] #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1e5 + 10; const int INF = 0x3f3f3f3f; int h[N], e[N], w[N], ne[N], idx; int n, m; int d[N]; int q[N], hh, tt = -1; 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(d, 0x3f, sizeof d); d[1] = 0; q[++tt] = 1; st[1] = true; while(tt >= hh) { int u = q[hh++]; st[u] = false; for(int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if(d[j] > d[u] + w[i]) { d[j] = d[u] + w[i]; if(!st[j]) { // 为了防止已在队列中的点, 被重复添加进队列 // 虽然不影响最终结果, 但会拖慢一点性能 st[j] = true; q[++tt] = j; } } } } } int main() { memset(h, -1, sizeof h); scanf("%d%d", &n, &m); while(m--) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, z); } spfa(); if(d[n] != INF) printf("%d", d[n]); else printf("impossible"); return 0; } SPFA的好处：能解决无负权边的问题，也能解决有负权边的问题，并且效率还比较高。但是当需要求在走不超过k条边的最短路问题上，就只能用Bellman-Ford算法了。 练习题：[acwing - 852: spfa求负环][acwing - 851_ spfa] 基本思路是，添加一个变量`int ctn[N]`，来记录走到第`i`个点所经过的边的长度即可，如果走到某个点的边的个数大于n，则说明存在负权回路。题解思路可以参考https://www.acwing.com/solution/content/6336/。由于是求是否存在负环，而不是求从`1`号点能够走到的负权回路，所以我们要把全部点加入到队列。可以这样理解，在原图的基础上新建一个虚拟源点，从该点向其他所有点连一条权值为0的有向边。那么原图有负环等价于新图有负环。此时在新图上做spfa，将虚拟源点加入队列中。然后进行spfa的第一次迭代，这时会将所有点的距离更新并将所有点插入队列中。执行到这一步，就等价于下面代码的做法了。 #include<iostream> #include<cstring> using namespace std; const int N = 1e4 + 10, M = 1e8 + 10; const int INF = 0x3f3f3f3f; int h[N], e[N], w[N], ne[N], idx; int n, m; int d[N], ctn[N]; bool st[N]; int q[M], hh, tt = -1; void add(int a, int b, int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; } bool spfa() { for(int i = 1; i <= n; i++) { q[++tt] = i; st[i] = true; } while(tt >= hh) { int u = q[hh++]; st[u] = false; for(int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if(d[j] > d[u] + w[i]) { d[j] = d[u] + w[i]; ctn[j] = ctn[u] + 1; if(ctn[j] >= n) return true; if(!st[j]) { q[++tt] = j; st[j] = true; } } } } return false; } int main() { memset(h, -1, sizeof h); scanf("%d%d", &n, &m); while(m--) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, z); } if(spfa()) printf("Yes"); else printf("No"); return 0; } 其实这道题用Bellman-Ford来做，思路更简单 #include<iostream> #include<cstring> using namespace std; const int N = 1e5; int n, m; struct Edge { int a, b, w; } edges[N]; int d[N], tmp[N]; bool bellman_ford() { for(int i = 1; i <= n; i++) { memcpy(tmp, d, sizeof d); for(int j = 0; j < m; j++) { Edge e = edges[j]; int a = e.a, b = e.b, w = e.w; if(d[b] > tmp[a] + w) { d[b] = tmp[a] + w; if(i == n) return true; } } } return false; } // bellman-ford判断负环 int main() { scanf("%d%d", &n, &m); for(int i = 0; i < m; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); edges[i] = { x, y, z}; } if(bellman_ford()) printf("Yes"); else printf("No"); return 0; } #### Floyd #### 求解多源汇最短路问题，也能处理边权为负数的情况，但是无法处理存在负权回路的情况。 使用邻接矩阵来存储图。初始使用`d[i][j]`来存储这个图，存储所有的边 算法思路：三层循环 > for(k = 1; k <= n; k++) > > for(i = 1; i <= n; i++) > > for(j = 1; j <= n; j++) > > d\[i,j\] = min(d\[i,j\] , d\[i,k\] + d\[k,j\]) 循环结束后，`d[i][j]`存的就是点`i`到`j`的最短距离。 原理是基于动态规划（具体原理在后续的动态规划章节再做详解）。 其状态表示是：`d(k, i, j)`，从点`i`，只经过`1 ~ k`这些中间点，到达点`j`的最短距离 练习题：[acwing - 854: Floyd求最短路][acwing - 854_ Floyd] #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 210, INF = 0x3f3f3f3f; int g[N][N]; // 邻接矩阵存储 int n, m, k; void floyd() { for(int p = 1; p <= n; p++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(g[i][p] != INF && g[p][j] != INF) g[i][j] = min(g[i][j], g[i][p] + g[p][j]); } } } } int main() { scanf("%d%d%d", &n, &m, &k); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i == j) g[i][j] = 0; else g[i][j] = INF; } } while(m--) { int x, y, z; scanf("%d%d%d", &x, &y, &z); g[x][y] = min(g[x][y], z); // 处理重边 } floyd(); while(k--) { int x, y; scanf("%d%d", &x, &y); if(g[x][y] == INF) printf("impossible\n"); else printf("%d\n", g[x][y]); } return 0; } ### 总结 ### 几种求解最短路的算法，各自的思路都不太相同，现做一个简单的总结 * Dijkstra 只适用于**边权为正**的情况。是从**点的维度**出发，每次循环确定起点到某一个点的最短距离，循环n次，则确定全部n个点到起点的最短距离。其思想有点类似BFS或者贪心，每次选一个距离最小的点，很保守的一点点地往外扩张，而不像DFS一条路走到黑。 注意有一个集合`s`的概念，每轮循环确定了一个点的最短距离后，就把这个点加入集合`s`。集合`s`表示的就是当前哪些点已经确定了最短距离了。已经确定了的点，之后的循环就不再考虑它们了。 每次循环，从未确定最短距离的点中，找一个距离最小的点`a`，则点`a`的最短距离已经确定，将其加入集合`s`，随后用`a`点去更新其他点（准确的说是和`a`相连的那些点（`a`的出边））的距离，本轮循环结束。 实际代码中，我们用一个布尔类型的数组，来表示一个点是否加入了集合`s` 堆优化版的Dijkstra：优化的就是每轮循环，**选择一个距离最小的点**这一步，使用小根堆可以在O(1)的时间复杂度选出距离最小的点 在选取一个距离最小的点后，只需要更新这个点所有出边，连接的那些点即可。所以用**邻接表**来存储比较合适。而邻接表适合存储稀疏图。所以在稀疏图时，可以采用堆优化Dijkstra，使用邻接表来存储图。稠密图的情况，则选用朴素Dijkstra，使用邻接矩阵来存储图。 朴素Dijkstra的时间复杂度是O(n2)，堆优化Dijkstra的时间复杂度是O(mlogn) * Bellman-Ford 适用于**存在负权边**的情况。是从**边的维度**出发。首先还是初始化所有点的距离为正无穷，然后初始化起点的距离为0。 循环n次（准确地说应该是n-1次，因为只需要走n-1条边就能从1号点走到n号点），每次循环遍历所有的边（一个边用`[a, b, w]`表示，`a`点到`b`点，权重为`w`），每次更新这条边右端点（`b`点）的距离。`d[b] = min(d[b], d[a] + w)`。 其实只有当`d[a]`不是正无穷时，才需要更新。如果无脑更新，则当`d[a]`是正无穷，且`w`是负数的话，`d[b]`会被更新为一个比正无穷稍小一点的数，在实际编码中可能出错。而由于`d[a]`为正无穷（`a`点不可达），则其实`b`点应该也保持为正无穷（`b`点也不可达）。 Bellman-Ford可以用来求解，**经过不超过k条边的最短距离**。因为每次迭代，都是把边往前走了一步（对于那些`a`点不可达的边`[a, b, w]`，不更新`d[b]`）。需要注意，更新距离数组`d`时，需要提前备份一下`d`，并使用上一轮的备份来进行更新。这是为了防止串联更新的情况。 串联更新，就比如有3个点，2条边，`a -> b -> c`，则第一次循环时，先根据`[a, b]`这条边更新了`d[b]`，然后访问到`[b ,c]`这条边时又会更新`d[c]`，但第一次循环时，只走出去一条边，是不应当走到`c`点的。但如果直接使用`d`数组来更新，则访问`[b ,c]`这条边时，由于先前访问`[a, b]`时更新了`d[b]`，则这次使用了新的`d[b]`，则会更新`d[c]`。 串联更新会影响【第k次循环，找到不超过k条边的最短距离】这一语义。虽然它不会影响最终的最短距离。 另外，更新时的条件判断还要注意，需要特别关注**重边**的情况，说明如下 void bellman_ford() { // 循环k次 for(int i = 0; i < k; i++) { // 使用备份数组来进行更新, 以避免出现串联更新的情况, 串联更新会影响k次循环找到经过不超过k条边的最短距离的语义 memcpy(tmp, d, sizeof d); // 每次枚举全部边 for(int j = 0; j < m; j++) { int a = edges[j].a, b = edges[j].b, w = edges[j].w; if(tmp[a] != INF && d[b] > tmp[a] + w) { // 注意这里后面要用 d[b] > tmp[a] + w // 而不能用 tmp[b] > tmp[a] + w // 当a和b存在重边时, 需要保证用到的是最短的那条边 // 如果采用 tmp[b] > tmp[a] + w , 则无法保证这一点, 可自行验证 d[b] = tmp[a] + w; } } } } Bellman-Ford也能用来判断图中是否存在负权回路。上面说了，实际只需要循环n-1次，若第n次循环仍然执行了距离的更新，则说明，从1号点到另一个点的最短距离，经过了n条边，n条边，则路径上有n+1个点，而由于一共只有n个点，所以这n+1个点中一定有2个点相同，则这条最短距离的路径上存在一个环，并且只有当距离变小时，才会执行更新，那么说明这个环的权重是负的。 * SPFA SPFA是对Bellman-Ford的优化。上面我们知道，Bellman-Ford是每次遍历所有边，并更新`d[b] = min(d[b], d[a] + w)`。 初始时所有点的距离都是正无穷的，而根据上面的式子，一条边的`w`是不变的，则只有当一条边的`a`点的距离`d[a]`变小了，下一轮循环才有可能会更新`d[b]`。于是我们**只需要关注那些距离变小的点**即可。 则采用类似BFS的思路，使用一个队列来保存那些距离变小的点。其代码思路相比Bellman-Ford而言，非常简单。所以通常对于**存在负权边**的最短路问题，通常直接用SPFA（甚至不存在负权边的问题，也可以用SPFA）。只有当类似于【求不超过k条边的最短路问题】时，才需要用Bellman-Ford。 \*\*但是！SPFA无法用于存在负权回路的情况！\*\*因为SPFA是用一个队列来存储距离变小的点，若存在负权回路，则队列永远不会为空，会无限循环。而Bellman-Ford由于只循环n次，即使有负权回路，也不会出现死循环。 SPFA代码如下，非常简单。 void spfa() { memset(d, 0x3f, sizeof d); // 距离初始化为正无穷 d[1] = 0; // 起点距离为0 q[++tt] = 1; // 起点距离变小, 入队 while(tt >= hh) { // 当队列不空 int u = q[hh++]; // pop 队头 // 遍历所有出边, 进行可能的更新 for(int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if(d[j] > d[u] + w[i]) { // 一定要写这个判断, 因为d[a]变小后, 对于边[a, b, w], 不一定会保证d[b]也变小(可能b点有其他更短的路径) d[j] = d[u] + w[i]; q[++tt] = j; // j点距离变小了, 入队 } } } } **突然感受到SPFA的魅力，思路和代码都极其简洁。单源最短路问题可以直接用SPFA通吃！完全不用什么Dijkstra和Bellman-Ford！** 然而，通过几道练习题，当需要判断图中是否有负权回路时，还是Bellman-Ford比SPFA好用。 * Floyd 这个算法没怎么去细细研究其背后的数学原理（貌似是动态规划中的状态转移），暂时先留着，等学到后面dp的部分再来补。TODO (2021/07/07 更新) [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70]: /images/20221005/5dc64f79a419497dab677e468f3cdd08.png [acwing - 849_ Dijkstra_ I]: https://www.acwing.com/problem/content/851/ [acwing - 850_ Dijkstra_ II]: https://www.acwing.com/problem/content/852/ [acwing - 853_]: https://www.acwing.com/problem/content/855/ [acwing - 851_ spfa]: https://www.acwing.com/problem/content/853/ [acwing - 854_ Floyd]: https://www.acwing.com/problem/content/856/
相关 Acwing - 算法基础课 - 笔记（五） 文章目录 数据结构（二） Trie树 练习题：\[Acwing - 835: Trie字符串统计\](http 约定不等于承诺〃/ 2022年10月06日 04:59/ 0 赞/ 162 阅读
悠悠
àì夳堔傛蜴生んèń
今天药忘吃喽~
还没有评论，来说两句吧...