Bellman_ford 队列优化算法（又名SPFA）
https://www.programmercarl.com/kamacoder/0094.%E5%9F%8E%E5%B8%82%E9%97%B4%E8%B4%A7%E7%89%A9%E8%BF%90%E8%BE%93I-SPFA.html
本题我们来系统讲解 Bellman_ford 队列优化算法 ，也叫SPFA算法（Shortest Path Faster Algorithm）。
SPFA的称呼来自 1994年西南交通大学段凡丁的论文，其实Bellman_ford 提出后不久 （20世纪50年代末期） 就有队列优化的版本，国际上不承认这个算法是是国内提出的。 所以国际上一般称呼 该算法为 Bellman_ford 队列优化算法（Queue improved Bellman-Ford）
大家知道以上来历，知道 SPFA 和 Bellman_ford 队列优化算法 指的都是一个算法就好。
如果大家还不够了解 Bellman_ford 算法，强烈建议按照《代码随想录》的顺序学习，否则可能看不懂下面的讲解。
大家可以发现 Bellman_ford 算法每次松弛 都是对所有边进行松弛。
但真正有效的松弛，是基于已经计算过的节点在做的松弛。
给大家举一个例子：
本图中，对所有边进行松弛，真正有效的松弛，只有松弛 边（节点1->节点2） 和 边（节点1->节点3） 。
而松弛 边（节点4->节点6） ，边（节点5->节点3）等等 都是无效的操作，因为 节点4 和 节点 5 都是没有被计算过的节点。
所以 Bellman_ford 算法 每次都是对所有边进行松弛，其实是多做了一些无用功。
只需要对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛就够了。
基于以上思路，如何记录 上次松弛的时候更新过的节点呢？
用队列来记录。（其实用栈也行，对元素顺序没有要求）
#模拟过程
接下来来举例这个队列是如何工作的。
以示例给出的所有边为例：
5 6 -2 1 2 1 5 3 1 2 5 2 2 4 -3 4 6 4 1 3 51
2
3
4
5
6
7我们依然使用minDist数组来表达 起点到各个节点的最短距离，例如minDist[3] = 5 表示起点到达节点3 的最小距离为5
初始化，起点为节点1， 起点到起点的最短距离为0，所以minDist[1] 为 0。 将节点1 加入队列 （下次松弛从节点1开始）
从队列里取出节点1，松弛节点1 作为出发点连接的边（节点1 -> 节点2）和边（节点1 -> 节点3）
边：节点1 -> 节点2，权值为1 ，minDist[2] > minDist[1] + 1 ，更新 minDist[2] = minDist[1] + 1 = 0 + 1 = 1 。
边：节点1 -> 节点3，权值为5 ，minDist[3] > minDist[1] + 5，更新 minDist[3] = minDist[1] + 5 = 0 + 5 = 5。
将节点2、节点3 加入队列，如图：
从队列里取出节点2，松弛节点2 作为出发点连接的边（节点2 -> 节点4）和边（节点2 -> 节点5）
边：节点2 -> 节点4，权值为1 ，minDist[4] > minDist[2] + (-3) ，更新 minDist[4] = minDist[2] + (-3) = 1 + (-3) = -2 。
边：节点2 -> 节点5，权值为2 ，minDist[5] > minDist[2] + 2 ，更新 minDist[5] = minDist[2] + 2 = 1 + 2 = 3 。
将节点4，节点5 加入队列，如图：
从队列里出去节点3，松弛节点3 作为出发点连接的边。
因为没有从节点3作为出发点的边，所以这里就从队列里取出节点3就好，不用做其他操作，如图：
从队列中取出节点4，松弛节点4作为出发点连接的边（节点4 -> 节点6）
边：节点4 -> 节点6，权值为4 ，minDist[6] > minDist[4] + 4，更新 minDist[6] = minDist[4] + 4 = -2 + 4 = 2 。
将节点6加入队列
如图：
从队列中取出节点5，松弛节点5作为出发点连接的边（节点5 -> 节点3），边（节点5 -> 节点6）
边：节点5 -> 节点3，权值为1 ，minDist[3] > minDist[5] + 1 ，更新 minDist[3] = minDist[5] + 1 = 3 + 1 = 4
边：节点5 -> 节点6，权值为-2 ，minDist[6] > minDist[5] + (-2) ，更新 minDist[6] = minDist[5] + (-2) = 3 - 2 = 1
如图，将节点3加入队列，因为节点6已经在队列里，所以不用重复添加
所以我们在加入队列的过程可以有一个优化，用visited数组记录已经在队列里的元素，已经在队列的元素不用重复加入
从队列中取出节点6，松弛节点6 作为出发点连接的边。
节点6作为终点，没有可以出发的边。
同理从队列中取出节点3，也没有可以出发的边
所以直接从队列中取出，如图：
这样我们就完成了基于队列优化的bellman_ford的算法模拟过程。
大家可以发现 基于队列优化的算法，要比bellman_ford 算法 减少很多无用的松弛情况，特别是对于边数众多的大图 优化效果明显。
了解了大体流程，我们再看代码应该怎么写。
在上面模拟过程中，我们每次都要知道 一个节点作为出发点连接了哪些节点。
如果想方便知道这些数据，就需要使用邻接表来存储这个图，如果对于邻接表不了解的话，可以看 kama0047.参会dijkstra堆 中 图的存储 部分。
思路
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
#define MAXN 1000 // 假设最大节点数为1000
#define MAXM 10000 // 假设最大边数为10000
typedef struct Edge {
int to; // 链接的节点
int val; // 边的权重
struct Edge* next; // 指向下一个边的指针
} Edge;
typedef struct {
Edge* head; // 邻接表的头
} Vertex;
// 创建一个新的边
Edge* createEdge(int to, int val) {
Edge* edge = (Edge*)malloc(sizeof(Edge));
edge->to = to;
edge->val = val;
edge->next = NULL;
return edge;
}
int main() {
int n, m, p1, p2, val;
scanf("%d %d", &n, &m);
Vertex graph[MAXN + 1]; // 邻接表
for (int i = 1; i <= n; i++) {
graph[i].head = NULL; // 初始化每个节点的头节点
}
// 将所有边保存起来
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &p1, &p2, &val);
Edge* edge = createEdge(p2, val);
edge->next = graph[p1].head; // 插入到邻接表的头部
graph[p1].head = edge;
}
int start = 1; // 起点
int end = n; // 终点
int minDist[MAXN + 1];
for (int i = 1; i <= n; i++) {
minDist[i] = INT_MAX; // 初始化为无穷大
}
minDist[start] = 0; // 起点到自身的距离为0
int queue[MAXN]; // FIFO 队列
int front = 0, rear = 0; // 队列的前端和后端
bool isInQueue[MAXN + 1] = {false}; // 标记节点是否在队列中
queue[rear++] = start; // 将起点加入队列
isInQueue[start] = true;
while (front < rear) {
int node = queue[front++]; // 从队列中取出节点
isInQueue[node] = false; // 取消标记
for (Edge* edge = graph[node].head; edge != NULL; edge = edge->next) {
int to = edge->to; // 获取目的节点
int value = edge->val; // 获取边的权重
// 松弛操作
if (minDist[to] > minDist[node] + value) {
minDist[to] = minDist[node] + value;
if (!isInQueue[to]) { // 只有不在队列中的节点才加入
queue[rear++] = to; // 加入队列
isInQueue[to] = true;
}
}
}
}
// 输出结果
if (minDist[end] == INT_MAX) {
printf("unconnected\n"); // 不能到达终点
} else {
printf("%d\n", minDist[end]); // 到达终点最短路径
}
// 释放分配的内存
for (int i = 1; i <= n; i++) {
Edge* edge = graph[i].head;
while (edge != NULL) {
Edge* temp = edge;
edge = edge->next;
free(temp);
}
}
return 0;
}学习反思
实现了使用邻接表来存储图，并利用BFS算法求解起点到终点的最短路径。
代码的主要思路如下：
- 定义了Edge结构体表示边，Vertex结构体表示节点。
- 创建了一个新的边的函数createEdge()，用于分配内存并初始化边的属性。
- 读取输入的节点数和边数，并创建邻接表graph。
- 使用for循环将所有边保存到邻接表中。
- 设置起点和终点，初始化最短路径数组minDist。
- 使用FIFO队列和BFS算法求解最短路径。
- 输出结果。
- 释放动态分配的内存。
这段代码的时间复杂度为O(n+m)，其中n为节点数，m为边数。空间复杂度为O(n)。
bellman_ford之判断负权回路
https://www.programmercarl.com/kamacoder/0095.%E5%9F%8E%E5%B8%82%E9%97%B4%E8%B4%A7%E7%89%A9%E8%BF%90%E8%BE%93II.html
本题是 kama94.城市间货物运输I 延伸题目。
本题是要我们判断 负权回路，也就是图中出现环且环上的边总权值为负数。
如果在这样的图中求最短路的话， 就会在这个环里无限循环 （也是负数+负数 只会越来越小），无法求出最短路径。
所以对于 在有负权值的图中求最短路，都需要先看看这个图里有没有负权回路。
接下来我们来看 如何使用 bellman_ford 算法来判断 负权回路。
在 kama94.城市间货物运输I 中 我们讲了 bellman_ford 算法的核心就是一句话：对 所有边 进行 n-1 次松弛。 同时文中的 【拓展】部分， 我们也讲了 松弛n次以上 会怎么样？
在没有负权回路的图中，松弛 n 次以上 ，结果不会有变化。
但本题有 负权回路，如果松弛 n 次，结果就会有变化了，因为 有负权回路 就是可以无限最短路径（一直绕圈，就可以一直得到无限小的最短距离）。
那么每松弛一次，都会更新最短路径，所以结果会一直有变化。
（如果对于 bellman_ford 不了解的录友，建议详细看这里：kama94.城市间货物运输I）
以上为理论分析，接下来我们再画图举例。
我们拿题目中示例来画一个图：
图中 节点1 到 节点4 的最短路径是多少（题目中的最低运输成本） （注意边可以为负数的）
节点1 -> 节点2 -> 节点3 -> 节点4，这样的路径总成本为 -1 + 1 + 1 = 1
而图中有负权回路：
那么我们在负权回路中多绕一圈，我们的最短路径 是不是就更小了 （也就是更低的运输成本）
节点1 -> 节点2 -> 节点3 -> 节点1 -> 节点2 -> 节点3 -> 节点4，这样的路径总成本 (-1) + 1 + (-1) + (-1) + 1 + (-1) + 1 = -1
如果在负权回路多绕两圈，三圈，无穷圈，那么我们的总成本就会无限小， 如果要求最小成本的话，你会发现本题就无解了。
在 bellman_ford 算法中，松弛 n-1 次所有的边 就可以求得 起点到任何节点的最短路径，松弛 n 次以上，minDist数组（记录起到到其他节点的最短距离）中的结果也不会有改变 （如果对 bellman_ford 算法 不了解，也不知道 minDist 是什么，建议详看上篇讲解kama94.城市间货物运输I）
而本题有负权回路的情况下，一直都会有更短的最短路，所以 松弛 第n次，minDist数组 也会发生改变。
那么解决本题的 核心思路，就是在 kama94.城市间货物运输I 的基础上，再多松弛一次，看minDist数组 是否发生变化。
思路
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
#define MAXN 1000 // 假设最大节点数
#define MAXM 10000 // 假设最大边数
typedef struct {
int from; // 边的起点
int to; // 边的终点
int weight; // 边的权重
} Edge;
int main() {
int n, m, p1, p2, val;
scanf("%d %d", &n, &m);
Edge edges[MAXM]; // 存储所有边
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &p1, &p2, &val);
edges[i].from = p1;
edges[i].to = p2;
edges[i].weight = val;
}
int start = 1; // 起点
int end = n; // 终点
// 存储从起点到每个节点的最短距离
int minDist[MAXN + 1];
for (int i = 1; i <= n; i++) {
minDist[i] = INT_MAX; // 初始化为无穷大
}
minDist[start] = 0; // 起点到自身的距离为0
bool flag = false; // 标记是否存在负权回路
for (int i = 1; i <= n; i++) { // 松弛n次
for (int j = 0; j < m; j++) {
int from = edges[j].from;
int to = edges[j].to;
int weight = edges[j].weight;
if (i < n) {
// 前n-1次，进行正常的松弛
if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + weight) {
minDist[to] = minDist[from] + weight;
}
} else {
// 第n次，检查是否存在负权回路
if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + weight) {
flag = true;
}
}
}
}
// 输出结果
if (flag) {
printf("circle\n"); // 存在负权回路
} else if (minDist[end] == INT_MAX) {
printf("unconnected\n"); // 不能到达终点
} else {
printf("%d\n", minDist[end]); // 到达终点的最短路径
}
return 0;
}学习反思
代码是求解带权有向图的单源最短路径问题，使用了Bellman-Ford算法。
算法的思想是从起点开始，进行n-1次松弛操作，每次松弛都尝试通过当前节点更新到达其他节点的最短路径长度。最后，再进行一次松弛操作，如果还能通过该操作更新最短路径，则说明存在负权回路。
具体实现上，通过一个长度为n的数组minDist[]来记录从起点到各个节点的最短路径长度，初始化为INT_MAX，表示无穷大。
在每次松弛操作中，遍历所有边，如果从起点到当前边的起点的路径长度不为无穷大，并且通过该边可以更新到达当前边终点的最短路径长度，则更新minDist[]数组的值。
在最后一次松弛操作中，如果还可以更新最短路径，则说明存在负权回路。
最后根据minDist[end]的值来判断结果，如果为INT_MAX，则说明无法到达终点；如果为负数，则说明存在负权回路；否则，表示到达终点的最短路径长度。
这段代码的时间复杂度为O(nm)，其中n为节点数，m为边数。
bellman_ford之单源有限最短路
https://www.programmercarl.com/kamacoder/0096.%E5%9F%8E%E5%B8%82%E9%97%B4%E8%B4%A7%E7%89%A9%E8%BF%90%E8%BE%93III.html
思路
本题为单源有限最短路问题，同样是 kama94.城市间货物运输I 延伸题目。
注意题目中描述是 最多经过 k 个城市的条件下，而不是一定经过k个城市，也可以经过的城市数量比k小，但要最短的路径。
在 kama94.城市间货物运输I 中我们讲了：对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。
节点数量为n，起点到终点，最多是 n-1 条边相连。 那么对所有边松弛 n-1 次 就一定能得到 起点到达 终点的最短距离。
（如果对以上讲解看不懂，建议详看 kama94.城市间货物运输I ）
本题是最多经过 k 个城市， 那么是 k + 1条边相连的节点。 这里可能有录友想不懂为什么是k + 1，来看这个图：
图中，节点1 最多已经经过2个节点 到达节点4，那么中间是有多少条边呢，是 3 条边对吧。
所以本题就是求：起点最多经过k + 1 条边到达终点的最短距离。
对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离，那么对所有边松弛 k + 1次，就是求 起点到达 与起点k + 1条边相连的节点的 最短距离。
注意： 本题是 kama94.城市间货物运输I 的拓展题，如果对 bellman_ford 没有深入了解，强烈建议先看 kama94.城市间货物运输I 再做本题。
思路
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAXN 1000 // 假设最大节点数
#define MAXM 10000 // 假设最大边数
typedef struct {
int from; // 边的起点
int to; // 边的终点
int weight; // 边的权重
} Edge;
int main() {
int src, dst, k, p1, p2, val, m, n;
// 读取节点数和边数
scanf("%d %d", &n, &m);
Edge edges[MAXM]; // 用于存储所有边
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &p1, &p2, &val);
edges[i].from = p1;
edges[i].to = p2;
edges[i].weight = val;
}
// 读取源节点、目标节点和最大边数k
scanf("%d %d %d", &src, &dst, &k);
// 存储从源节点到每个节点的最短距离
int minDist[MAXN + 1];
for (int i = 1; i <= n; i++) {
minDist[i] = INT_MAX; // 初始化为无穷大
}
minDist[src] = 0; // 源节点到自身的距离为0
// 松弛k + 1次
for (int i = 1; i <= k + 1; i++) {
int tempDist[MAXN + 1]; // 用于存储当前迭代的最短距离
for (int j = 1; j <= n; j++) {
tempDist[j] = minDist[j]; // 初始化临时数组
}
// 遍历所有边进行松弛
for (int j = 0; j < m; j++) {
int from = edges[j].from;
int to = edges[j].to;
int weight = edges[j].weight;
if (tempDist[from] != INT_MAX && tempDist[to] > tempDist[from] + weight) {
tempDist[to] = tempDist[from] + weight; // 更新最短路径
}
}
// 将当前迭代的结果更新到minDist
for (int j = 1; j <= n; j++) {
minDist[j] = tempDist[j];
}
}
// 输出结果
if (minDist[dst] == INT_MAX) {
printf("unreachable\n"); // 不能到达目标节点
} else {
printf("%d\n", minDist[dst]); // 到达目标节点的最短路径
}
return 0;
}学习反思
实现了求解单源最短路径问题的算法，采用了Bellman-Ford算法的思想。
首先，通过scanf函数读入节点数n和边数m。
然后，定义了一个结构体Edge用于存储边的信息，包括边的起点、终点和权重。
接下来，使用for循环读入m条边的信息，并将其存储到edges数组中。
再次使用scanf函数读入源节点src、目标节点dst和最大边数k。
然后，定义了一个数组minDist用于存储从源节点到每个节点的最短距离，初始值为无穷大。
接下来，进行k + 1次松弛操作，每次遍历所有边，如果发现存在从from节点到to节点的距离更短的路径，则更新最短距离。
最后，判断到达目标节点的最短路径是否存在，如果不存在则输出"unreachable"，否则输出最短路径的值。
该算法的时间复杂度为O(k * m)，其中k为最大边数，m为边数。
