代码随想录算法训练营 Day60 图论Ⅹ Bellmen_ford 系列算法

图论

题目

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 <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>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<list<Edge>> grid(n+1);vector<bool> isInQueue(n+1);// 构造邻接表for (int i = 0; i < m; ++i) {cin >> x >> y >> val;grid[x].push_back({Edge(y, val)});}int start = 1;int end = n;vector<int> minDist(n+1, INT_MAX);minDist[start] = 0;queue<int> 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 << "unconnected" << endl;else cout << minDist[end] << endl;return 0;
}

95. 城市间货物运输 II
涉及到负权回路的情况（存在环路，权值为负，会导致无限循环值越来越小）
非负权回路，松弛 n-1 次以上不会有变换，但是设计负权回路就会越来越小

那么解决本题的核心思路，就是在 kama94.城市间货物运输I 的基础上，再多松弛一次，看minDist数组是否发生变化。 如果再松弛一次结果变换则存在负权回路

// Bellman_ford 算法实现
#include <iostream>
#include <vector>
#include <climits>using namespace std;int main() {int n, m, x, y, val;cin >> n >> m;vector<vector<int>> grid;vector<int> minDist(n+1, INT_MAX);for (int i = 0; i < m; ++i) {cin >> 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 <= n; ++i) {for (vector<int>& edge : grid) {int from = edge[0];int to = edge[1];int price = edge[2];if (i < n) {if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) {minDist[to] = minDist[from] + price;}}else {if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) isCircle = true;}}}if (isCircle) cout << "circle" << endl;else if (minDist[end] == INT_MAX) cout << "unconnected" << endl;else cout << minDist[end] << endl;return 0;
}// Bellman_ford 队列优化版本 SPFA 实现
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>
using namespace std;struct Edge { //邻接表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<list<Edge>> grid(n + 1); // 邻接表// 将所有边保存起来for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;// p1 指向 p2，权值为 valgrid[p1].push_back(Edge(p2, val));}int start = 1;  // 起点int end = n;    // 终点vector<int> minDist(n + 1 , INT_MAX);minDist[start] = 0;queue<int> que;que.push(start); // 队列里放入起点 vector<int> count(n+1, 0); // 记录节点加入队列几次count[start]++;vector<bool> 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 << "circle" << endl;else if (minDist[end] == INT_MAX) {cout << "unconnected" << endl;} else {cout << minDist[end] << endl;}}

96. 城市间货物运输 III
给出尽可能路过最多城市的最短路径
本题是最多经过 k 个城市， 那么是 k + 1条边相连的节点。 这里可能有录友想不懂为什么是k + 1，来看这个图
节点1 最多已经经过2个节点 到达节点4，那么中间是有多少条边呢，是 3 条边对吧。
所以本题就是求：起点最多经过k + 1 条边到达终点的最短距离。
对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离，那么对所有边松弛 k + 1次，就是求起点到达与起点k + 1条边相连的节点的最短距离。 理解以上内容，其实本题代码就很容易了，bellman_ford 标准写法是松弛 n-1 次，本题就松弛 k + 1次就好。
但是松弛 k + 1次代码有错，具体分析如下
起点为节点1，起点到起点的距离为0，所以 minDist[1] 初始化为0 ，如图

其他节点对应的minDist初始化为max，因为我们要求最小距离，那么还没有计算过的节点默认是一个最大数，这样才能更新最小距离。当我们开始对所有边开始第一次松弛：边：节点1 -> 节点2，权值为-1 ，minDist[2] > minDist[1] + (-1)，更新 minDist[2] = minDist[1] + (-1) = 0 - 1 = -1

边：节点2 -> 节点3，权值为1 ，minDist[3] > minDist[2] + 1 ，更新 minDist[3] = minDist[2] + 1 = -1 + 1 = 0 ，如图

边：节点3 -> 节点1，权值为-1 ，minDist[1] > 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 <iostream>
#include <vector>
#include <climits>using namespace std;int main() {int n, m, x, y, val, src, dst, k;cin >> n >> m;vector<vector<int>> grid;vector<int> minDist(n+1, INT_MAX);vector<int> minDistCopy(n+1);for (int i = 0; i < m; ++i) { cin >> x >> y >> val;grid.push_back({x, y, val});}cin >> src >> dst >> k;minDist[src] = 0;// 最多经过k个城市，最多走过k+1条边for (int i = 1; i <= k + 1; ++i) {// 获取上一次计算结果minDistCopy = minDist;for (vector<int>& side : grid) {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 << "unreachable" << endl;else cout << minDist[dst] << endl;
}// bellman_ford 队列优化 SPFA
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>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, src, dst, k;cin >> n >> m;vector<list<Edge>> grid(n+1);vector<int> minDist(n+1, INT_MAX);vector<int> minDistCopy(n+1);for (int i = 0; i < m; ++i) {cin >> x >> y >> val;grid[x].push_back(Edge(y, val));}cin >> src >> dst >> k;k++; // k+1minDist[src] = 0;queue<int> que;que.push(src);// k控制松弛次数int qSize = 0;while (k-- && !que.empty()) {// 开启新的队列vector<bool> 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 << "unreachable" << endl;else cout << minDist[dst] << endl;
}

边的顺序会影响每一次扩展的结果，给出边的顺序为
我上面讲解中，给出的示例是这样的：

4 4
1 2 -1
2 3 1
3 1 -1
3 4 1
1 4 3

我将示例中边的顺序改一下，给成：

4 4
3 1 -1
3 4 1
2 3 1
1 2 -1
1 4 3

相同的图就会有不同的结果

推理一遍，初始化

边：节点3 -> 节点1，权值为-1 ，节点3还没有被计算过，节点1 不更新。
边：节点3 -> 节点4，权值为1 ，节点3还没有被计算过，节点4 不更新。
边：节点2 -> 节点3，权值为 1 ，节点2还没有被计算过，节点3 不更新。
边：节点1 -> 节点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 贪心策略导致找不到
参考：代码随想录