代码随想录算法训练营 Day60 图论Ⅹ Bellmen
图论
题目
94. 城市间货物运输 I
Bellmen_ford 队列优化算法 SPFA
大家可以发现 Bellman_ford 算法每次松弛 都是对所有边进行松弛。
但真正有效的松弛，是基于已经计算过的节点在做的松弛。 
本图中，对所有边进行松弛，真正有效的松弛，只有松弛边（节点1->节点2） 和边（节点1->节点3） 因此只要记录上一次松驰过的边即可
模拟过程
我们依然使用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 算法减少很多无用的松弛情况，特别是对于边数众多的大图优化效果明显。
代码实现类似于 dijkstra 的优化版本，需要将图以邻接表的形式构建
#include
#include
#include
#include
#include
using namespace std;
struct Edge {
int to;
int val;
Edge(int t, int w): to(t), val(w) {}
};
int main() {
int n, m, x, y, val;
cin >> n >> m;
vector grid(n+1);
vector isInQueue(n+1);
// 构造邻接表
for (int i = 0; i > x >> y >> val;
grid[x].push_back({Edge(y, val)});
}
int start = 1;
int end = n;
vector minDist(n+1, INT_MAX);
minDist[start] = 0;
queue que;
que.push(start);
// 使用队列
while (!que.empty()) {
int cur = que.front();
// 从队列里取出的时候，要取消标记，我们只保证已经在队列里的元素不用重复加入
isInQueue[cur] = false;
que.pop();
for (Edge e : grid[cur]) {
int from = cur;
int to = e.to;
int price = e.val;
if (minDist[to] > minDist[from] + price) {
minDist[to] = minDist[from] + price;
// 不再添加to这个下标元素 相当于已经访问过
if (isInQueue[to] == false) {
que.push(to);
isInQueue[to] = true;
}
}
}
}
if(minDist[end] == INT_MAX) cout
int n, m, x, y, val;
cin n m;
vector grid;
vector minDist(n+1, INT_MAX);
for (int i = 0; i > x >> y >> val;
grid.push_back({x, y, val});
}
int start = 1;
int end = n;
bool isCircle = false;
minDist[start] = 0;
// 多做一次负权回路
for (int i = 1; i
for (vector
int from = edge[0];
int to = edge[1];
int price = edge[2];
if (i minDist[from] + price) isCircle = true;
}
}
}
if (isCircle) cout //邻接表
int to; // 链接的节点
int val; // 边的权重
Edge(int t, int w): to(t), val(w) {} // 构造函数
};
int main() {
int n, m, p1, p2, val;
cin n m;
vector
cin p1 >> p2 >> val;
// p1 指向 p2，权值为 val
grid[p1].push_back(Edge(p2, val));
}
int start = 1; // 起点
int end = n; // 终点
vector minDist(n + 1 , INT_MAX);
minDist[start] = 0;
queue que;
que.push(start); // 队列里放入起点
vector count(n+1, 0); // 记录节点加入队列几次
count[start]++;
vector isInQueue(n+1, false);
isInQueue[start] = true;
bool flag = false;
while (!que.empty()) {
int node = que.front(); que.pop();
isInQueue[node] = false;
for (Edge edge : grid[node]) {
int from = node;
int to = edge.to;
int value = edge.val;
if (minDist[to] > minDist[from] + value) { // 开始松弛
minDist[to] = minDist[from] + value;
if (!isInQueue[to]) {
que.push(to);
isInQueue[to] = true;
count[to]++;
if (count[to] == n) {// 如果加入队列次数超过 n-1次 就说明该图与负权回路
flag = true;
while (!que.empty()) que.pop();
break;
}
}
}
}
}
if (flag) cout
cout
cout minDist[3] + (-1)，更新 minDist[1] = 0 + (-1) = -1 ，如图：
边：节点3 -> 节点4，权值为1 ，minDist[4] > minDist[3] + 1，更新 minDist[4] = 0 + 1 = 1 ，如图：
理论上来说，对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。
而且对所有边的后面几次松弛，同样是更新了所有的节点，说明至多经过k 个节点这个限制根本没有限制住，每个节点的数值都被更新了。
这是为什么？
在上面画图距离中，对所有边进行第一次松弛，在计算边（节点2 -> 节点3） 的时候，更新了节点3。
理论上来说节点3 应该在对所有边第二次松弛的时候才更新。 这因为当时是基于已经计算好的 节点2（minDist[2]）来做计算了。minDist[2]在计算边：（节点1 -> 节点2）的时候刚刚被赋值为 -1。
这样就造成了一个情况，即：计算minDist数组的时候，基于了本次松弛的 minDist数值，而不是上一次松弛时候minDist的数值。所以在每次计算 minDist 时候，要基于 对所有边上一次松弛的 minDist 数值才行，所以我们要记录上一次松弛的minDist。
具体代码添加了 minDist 的 copy
// 朴素 Bellman_ford方法
#include
#include
#include
using namespace std;
int main() {
int n, m, x, y, val, src, dst, k;
cin >> n >> m;
vector grid;
vector minDist(n+1, INT_MAX);
vector minDistCopy(n+1);
for (int i = 0; i > x >> y >> val;
grid.push_back({x, y, val});
}
cin >> src >> dst >> k;
minDist[src] = 0;
// 最多经过k个城市，最多走过k+1条边
for (int i = 1; i
// 获取上一次计算结果
minDistCopy = minDist;
for (vector
int from = side[0];
int to = side[1];
int price = side[2];
// 使用上一次copy计算
if (minDistCopy[from] != INT_MAX && minDist[to] minDistCopy[from] + price) {
minDist[to] = minDistCopy[from] + price;
}
}
}
if (minDist[dst] == INT_MAX) cout
int to;
int val;
Edge(int t, int w) : to(t), val(w) {}
};
int main() {
int n, m, x, y, val, src, dst, k;
cin n m;
vector grid(n+1);
vector minDist(n+1, INT_MAX);
vector minDistCopy(n+1);
for (int i = 0; i > x >> y >> val;
grid[x].push_back(Edge(y, val));
}
cin >> src >> dst >> k;
k++; // k+1
minDist[src] = 0;
queue que;
que.push(src);
// k控制松弛次数
int qSize = 0;
while (k-- && !que.empty()) {
// 开启新的队列
vector isInQueue(n+1, false);
minDistCopy = minDist;
qSize = que.size();
// 后--保证执行完全
while (qSize--) {
int cur = que.front();
que.pop();
isInQueue[cur] = false;
for (Edge e : grid[cur]) {
int from = cur;
int to = e.to;
int price = e.val;
if (minDist[to] > minDistCopy[from] + price) {
minDist[to] = minDistCopy[from] + price;
if (!isInQueue[to]) {
que.push(to);
isInQueue[to] = true;
}
}
}
}
}
if (minDist[dst] == INT_MAX) cout 节点2，权值为 -1 ，minDist[2] > minDist[1] + (-1)，更新 minDist[2] = 0 + (-1) = -1
可以发现 同样的图，边的顺序不一样，使用版本一的代码 每次松弛更新的节点也是不一样的。
而边的顺序是随机的，是题目给我们的，所以本题我们才需要 记录上一次松弛的minDist，来保障 每一次对所有边松弛的结果。
为什么必须使用 copy？
94.城市间货物运输I，是没有负权回路的，那么多松弛多少次，对结果都没有影响。求节点1 到 节点n 的最短路径，松弛n-1 次就够了，松弛 大于 n-1次，结果也不会变。 那么在对所有边进行第一次松弛的时候，如果基于本次计算的 minDist 来计算 minDist （相当于多做松弛了），也是对最终结果没影响。
95.城市间货物运输II 是判断是否有负权回路，一旦有负权回路，对所有边松弛 n-1 次以后，在做松弛 minDist 数值一定会变，根据这一点来判断是否有负权回路。所以，95.城市间货物运输II 只需要判断minDist数值变化了就行，而 minDist 的数值对不对，并不是我们关心的。
其关键在于本题的两个因素：
本题可以有负权回路，说明只要多做松弛，结果是会变的。
本题要求最多经过 k 个节点，对松弛次数是有限制的。
可以使用 dijkstra 吗？不可以因为 dijkstra 贪心策略导致找不到
参考：代码随想录
