代码随想录算法训练day66---图论系列10《Bellman_ford 队列优化算法负权回路单源有限最短路》

代码随想录算法训练

—day66

前言

今天是算法营的第66天，希望自己能够坚持下来！
今天继续图论part！今日任务：
● Bellman_ford 队列优化算法（又名SPFA）
●bellman_ford之判断负权回路
●bellman_ford之单源有限最短路

一、94. 城市间货物运输 I—Bellman_ford 队列优化算法（又名SPFA）

卡码网题目链接
文章讲解

Bellman_ford 算法每次松弛 都是对所有边进行松弛。
但真正有效的松弛，是基于已经计算过的节点在做的松弛。
所以其实只需要对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛就够了。

那么怎么知道上次松弛更新的节点呢？用队列记录。（其实用栈也行，对元素顺序没有要求）

思路：
1.用队列记录上次松弛更新的节点，每次从队列弹出节点去找当前节点连接的所有节点来更新minDist。
2.因为需要找当前节点连接的所有节点，那么用邻接表会方便一些
3.因为有权值，所以定义一个Edge结构体比较方便
4.再加一个bool数组来标记已经在列表中的节点，避免重复加入队列

代码如下：

#include<iostream>
#include<vector>
#include<list>
#include<climits>
#include<queue>
using namespace std;
 
struct Edge { //邻接表
    int to; //链接的节点
    int val; //边的权重
 
    Edge(int t, int v): to(t), val(v) {} //构造函数
};
 
int main() 
{
    int n, m, p1, p2, val;
 
    cin >> n >> m;
    vector<list<Edge>> grid(n+1);
    vector<bool> isInQueue(n+1); //加入优化， 已经在队列里的元素不用重复添加
 
    //将所有边保存起来
    while (m--) {
        cin >> p1 >> p2 >> val;
        grid[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);
 
    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;
                }
            }
        }
    }
    if (minDist[end] == INT_MAX) cout << "unconnected" << endl;
    else  cout << minDist[end] << endl;
}

二、95. 城市间货物运输 II—bellman_ford之判断负权回路

卡码网题目链接
文章讲解

本题因为存在负权回路，如果用上面的方法，会导致一直在负权回路中循环找最小值而进入死循环。

在没有负权回路的图中，松弛 n 次以上 ，结果不会有变化。
而如果有负权回路的话，松弛 n 次结果就会有变化。

所以我们松弛n次，然后在第n次时候加入一个flag判断就可以了。

代码如下：

#include<iostream>
#include<vector>
#include<climits>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;
    vector<vector<int>> grid;

    while (m--) {
        cin >> p1 >> p2 >> val;
        grid.push_back({p1, p2, val});
    }

    int start = 1;
    int end = n;
    vector<int> minDist(n+1, INT_MAX);
    minDist[start] = 0;

    bool flag = false;
    for (int i = 1; i <= n; i++) { // 这里我们松弛n次，最后一次判断负权回路
        for (vector<int>&side : grid) {
            int from = side[0];
            int to = side[1];
            int value = side[2];

            if (i < n) {
                if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + value) {
                    minDist[to] = minDist[from] + value;
                }
            } else { // 多加一次松弛判断负权回路
                if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + value) {
                    flag = true;
                }
            }
        }
    }

    if (flag) cout << "circle" << endl;
    else if (minDist[end] == INT_MAX) cout << "unconnected" << endl;
    else cout << minDist[end] << endl;
}

三、96. 城市间货物运输 III—bellman_ford之单源有限最短路

卡码网题目链接
文章讲解

思路:

对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。
本题是最多经过 k 个城市， 那么是 k + 1条边相连的节点。

那么bellman_ford 标准写法是松弛 n-1 次，本题就松弛 k + 1次就好。
但是还需要考虑一个问题，负权回路。
如果存在负权回路的话，这样就造成了一个情况，
即：计算minDist数组的时候，基于了本次松弛的 minDist数值，而不是上一次 松弛时候minDist的数值。
所以在每次计算 minDist 时候，要基于 对所有边上一次松弛的 minDist 数值才行，所以我们要记录上一次松弛的minDist。

代码如下：

#include<iostream>
#include<vector>
#include<climits>
using namespace std;

int main() {
    int n, m, p1, p2, val, src, dst, k;

    cin >> n >> m;
    vector<vector<int>> grid;

    while (m--) {
        cin >> p1 >> p2 >> val;
        grid.push_back({p1, p2, val});
    }

    cin >> src >> dst >> k;

    vector<int> minDist(n + 1, INT_MAX);
    vector<int> minDist_copy(n + 1); //用来记录上一次遍历的结果
    minDist[src] = 0;

    for (int i = 1; i <= k + 1; i++) {
        minDist_copy = minDist; //获取上一次计算的结果
        for (vector<int>& side : grid) {
            int from = side[0];
            int to = side[1];
            int value = side[2];
            //注意使用minDist_copy来计算minDist
            if (minDist_copy[from] != INT_MAX && minDist[to] > minDist_copy[from] + value) {
                minDist[to] = minDist_copy[from] + value;
            }
        }
    }

    if (minDist[dst] == INT_MAX) cout << "unreachable" << endl;
    else cout << minDist[dst] <<endl;
}

总结

1.Bellman_ford 队列优化算法，使用队列保存上一次松弛更新的节点，使用bool
数组避免重复加入队列
2.bellman_ford之判断负权回路：对所有边进行n次松弛，在第n次时候判断是否仍然有变化，是则证明有回路。
3.bellman_ford之单源有限最短路：只能经过k个城市，那么就是k+1条边，对所有边进行k+1次松弛，其中需要注意的是，要用另外一个数组minDist_copy来保存上一次minDist，更新minDist时要用minDist_copy来计算。

明天继续加油！