Acwing Bellman-Ford SPFA

1. Bellman-Ford

该算法适用于有负权边的情况，注意：如果有负权环的话，最短路就不一定存在了。时间复杂度$O(mn).$该算法可以求出来图中是否存在负权回路，但求解负权回路，通常用SPFA算法，而不用Bell-Ford算法，因为前者的时间复杂度更低。

Bellman-ford不要求用邻接表或者邻接矩阵存储边，为简化操作，可以定义一个结构体，存储a，b，w。表示存在一条边a点指向b点，权重为w。则遍历所有边时，只要遍历全部的结构体数组即可

主要步骤：

• 循环n次：循环的次数的含义：假设循环了k次则表示：从起点经过不超过k条边，走到某个点的最短距离
• 每次循环，遍历图中的所有的边。对每条边(a,b,w),(指的是从a点到b点，权值是w的一条边）更新d[b] = min(d[b],d[a]+w)。该操作称为松弛操作。
• 该算法能够保证，在循环n次后，对所有的边(a,b,w),都满足d[b] <= d[a] + w。这个不等式被称为三角不等式。

ACwing 853. 有边数限制的最短路

实现思路：

• 利用上述的Bellman-ford算法
• 依旧定义一个距离数组dist,初始化未正无穷(0x3f3f3f3f)。注意最后判断到n号节点是否有路径不是直接判断dist[n] == 0x3f3f3f3f,因为存在负权边，可能更新的时候会存在dist[n] = 0x3f3f3f3f - c,即无穷大加上一个负数，仍为无穷大但数值还是改变了，所以最后有路径的判断改为dist[n] > 0x3f3f3f3f / 2.
• 本题要求1号到n号点不超过k条边的最短距离，则循环k次来寻找最短路；
• 每次再遍历m条边，判断加入当前点后，各店点到起点的距离是否变小，若变小则更新距离；
• 注意：该距离更新时可能会导致参与的边的数量大于k，因此应在每次遍历前设置一个备份数组backup,记录在k次遍历中，本次遍历的上一次的距离数组状态，在该次遍历中对每条边的距离数组更新时采用备份数组，确保本次更新范围在当前的边数限制内。

具体实现代码：`

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 510, M = 10010;int n, m, k; // n: 顶点数, m: 边数, k: 最多使用的边数
int dist[N], backup[N]; // dist: 存储当前节点的最短距离，backup: 每轮备份上一轮的最短距离// 定义一个结构体存储边的信息
struct Edge {int a, b, w; // a: 起点, b: 终点, w: 边的权重
} edges[M]; // 存储所有的边，最多 M 条// Bellman-Ford 算法的核心函数，返回 1 到 n 的最短距离
int bellman_ford() {// 初始化距离数组，将所有点的距离设置为一个非常大的值(无穷大)memset(dist, 0x3f, sizeof dist);dist[1] = 0; // 源点（起点）1到自己的距离为 0// Bellman-Ford 算法允许最多使用 k 条边来放松所有边for (int i = 0; i < k; i++) { // 执行 k 轮松弛操作memcpy(backup, dist, sizeof dist); // 将当前距离备份// 遍历每条边，尝试更新目标顶点的最短距离for (int j = 0; j < m; j++) {int a = edges[j].a, b = edges[j].b, w = edges[j].w; // 获取边的起点，终点和权重dist[b] = min(dist[b], backup[a] + w); // 更新顶点 b 的距离}}// 如果最终 dist[n] 的值仍然非常大，说明无法在 k 条边以内到达顶点 nif (dist[n] > 0x3f3f3f3f / 2) return -1; // 0x3f3f3f3f 是表示无穷大的近似值return dist[n]; // 返回最短路径距离
}int main() {cin >> n >> m >> k; // 读取顶点数 n, 边数 m 和最多可用边数 k// 读取每条边的起点、终点和权重，并存入 edges 数组for (int i = 0; i < m; i++) {int a, b, w;cin >> a >> b >> w;edges[i] = {a, b, w};}// 调用 bellman_ford 函数计算最短路径int t = bellman_ford();// 如果 t 返回 -1 且 dist[n] 不是 -1（没有负权环），输出 "impossible"if (t == -1 && dist[n] != -1) puts("impossible"); else cout << t << endl; // 否则输出最短路径的距离return 0;
}

2.SPFA

• 若要使用SPFA算法，一定要求图中不能有负权回路。只要图中没有负权回路，都可以用SPFA，即也可以求解正权边的题，这个算法的限制是比较小的。时间复杂度一般为$O(m)，$最差为$O(mn).$在一些情况下可以代替Dijkstra算法

• SPFA其实是对Bellman-Ford的一种优化，相比Bellman-Ford判环的时间复杂度也更低。 它优化的是这一步：d[b] =
  min (d[b],d[a] + w)

• 我们观察可以发现，只有当d[a]变小了，在下一轮循环中以a为起点的点（或者说a的出边）就会更新，即下一轮循环必定更新d[b]。

• 考虑用一个队列queue，来存放距离变小的节点(当图中存在负权回路时，队列永远都不会为空，因为总是存在某个点，在一次松弛操作后，距离变小）。

具体实现代码（详解版）：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int N = 100010;int e[N], ne[N], idx, w[N], h[N]; // e: 邻接点, ne: 下一条边的索引, 
//idx: 当前边的索引, w: 边的权重, h: 头节点int dist[N]; // 存储从起点 1 到每个节点的最短距离
int n, m; 
bool s[N]; // 记录节点是否在队列中，避免重复入队// 添加一条从 a 到 b 的边，权重为 c 的边
void add(int a, int b, int c) {e[idx] = b; // 终点 bne[idx] = h[a]; // 将边 idx 加到节点 a 的邻接表中w[idx] = c; // 边的权重h[a] = idx++; // 更新节点 a 的头指针，指向新加的边
}// SPFA 算法求解最短路径
int spfa() {memset(dist, 0x3f, sizeof dist); // 初始化距离为无穷大dist[1] = 0; // 起点 1 到自己的距离为 0queue<int> q; // 定义队列用于处理节点q.push(1); // 将起点 1 入队s[1] = true; // 标记起点 1 已入队// 队列不为空时进行循环while (q.size()) {auto t = q.front(); // 取出队首节点q.pop(); // 弹出队首节点s[t] = false; // 标记节点 t 不在队列中// 遍历节点 t 的所有邻接边for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i]; // 获取节点 t 的邻接点 j// 如果从节点 t 到 j 的路径更短，则更新 j 的距离if (dist[j] > dist[t] + w[i]) {dist[j] = dist[t] + w[i];// 如果节点 j 不在队列中，则将其加入队列if (!s[j]) {s[j] = true; // 标记节点 j 已入队q.push(j); // 节点 j 入队}}}}// 如果终点 n 的距离仍然为无穷大，表示无法到达，返回 -1if (dist[n] > 0x3f3f3f3f / 2) return -1;else return dist[n]; // 否则返回最短距离
}int main() {cin >> n >> m; // 输入节点数 n 和边数 mmemset(h, -1, sizeof h); // 初始化头节点数组为 -1，表示没有边// 读取每条边的信息，并调用 add 函数将其加入邻接表while (m--) {int a, b, w;cin >> a >> b >> w;add(a, b, w);}// 调用 spfa 函数计算最短路径int t = spfa();// 如果最短距离为 -1，且终点距离不为 -1，则输出 "impossible"if (t == -1 && dist[n] != -1) puts("impossible");else cout << t << endl; // 否则输出最短路径的距离return 0;
}