代码随想录day60图论10

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); 

    vector<bool> isInQueue(n + 1); // 加入优化，已经在队里里的元素不用重复添加

    // 将所有边保存起来
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // 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] == false) { // 已经在队列里的元素不用重复添加
                    que.push(to);
                    isInQueue[to] = true;
                }
            }
        }

    }
    if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点
    else cout << minDist[end] << endl; // 到达终点最短路径
}

95. 城市间货物运输 II

题目链接
文章讲解

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m; // 输入图的节点数n和边数m

    vector<vector<int>> grid; // 存储边的容器，每条边是一个包含 3 个元素的数组 {x, y, z}
    // 读取所有的边并存储
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;  // 读取一条边，起点为x，终点为y，边的权重为z
        grid.push_back({x, y, z});  // 将边存储到 grid 中
    }

    int ans = 0;  // 用来存储最终的答案
    vector<int> mindist(n + 1, INT_MAX);  // 初始化最短路径数组，初始时设置所有节点的最短路径为 INT_MAX
    mindist[1] = 0;  // 起点到自己的最短距离为0

    // Bellman-Ford算法的主循环：遍历n次更新所有节点的最短路径
    for (int i = 1; i <= n; i++) {
        // 对每条边进行松弛操作
        for (auto& j : grid) {
            int x = j[0];  // 起点
            int y = j[1];  // 终点
            int z = j[2];  // 边的权重

            // 松弛操作：如果从节点x到节点y的路径可以通过该边得到更短的路径
            if (mindist[x] != INT_MAX && mindist[x] + z < mindist[y]) {
                mindist[y] = mindist[x] + z;  // 更新最短路径
            }
        }

        // 记录在倒数第二次循环时的最短路径值（i == n-1）
        if (i == n - 1) ans = mindist[n];
    }

    // 判断是否有负权环（如果在最后一轮更新时还可以松弛路径，说明有负权环）
    if (mindist[n] < ans) {
        cout << "circle";  // 如果最终路径小于倒数第二次的路径，表示图中有负权环
    } else if (mindist[n] == INT_MAX) {
        cout << "unconnected";  // 如果目标节点 n 不可达，输出 "unconnected"
    } else {
        cout << ans;  // 输出从节点1到节点n的最短路径
    }
}

96. 城市间货物运输 III

题目链接
文章讲解

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m; // 输入城市数n和道路数m

    // 使用二维vector grid 存储所有的边，每个边是一个 {x, y, z} 三元组
    vector<vector<int>> grid;
    
    // 输入每条边的信息，并存储到 grid 中
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z; // 读取一条边，边从节点x到节点y，边权为z
        grid.push_back({x, y, z}); // 将这条边加入到 grid 中
    }

    int s, t, k;
    cin >> s >> t >> k; // 输入源城市s，目标城市t，最大经过k个城市的限制

    // 初始化mindist数组，所有城市的最短距离初始化为无穷大（INT_MAX）
    vector<int> mindist(n + 1, INT_MAX);
    vector<int> copy_mindist(n + 1);  // 用来存储前一轮的最短路径，避免重复修改
    mindist[s] = 0;  // 起点s到自己的最短路径为0

    k++;  // 因为k是经过的城市数量，最多经过k个城市相当于最多经过k+1条边

    // Bellman-Ford 算法，最多进行 k 次松弛操作
    // Bellman-Ford 算法的核心是：每次遍历所有的边，通过松弛操作更新最短路径
    while (k--) {
        // 在每次循环中，先复制一份当前的最短路径
        copy_mindist = mindist;

        // 遍历所有的边，进行松弛操作
        for (auto& j : grid) {
            int x = j[0];  // 边的起点
            int y = j[1];  // 边的终点
            int z = j[2];  // 边的权值（运输成本 - 补贴）

            // 如果从x到y的最短路径已知，且经过这条边可以得到更短的路径
            if (copy_mindist[x] != INT_MAX && mindist[y] > copy_mindist[x] + z) {
                mindist[y] = copy_mindist[x] + z;  // 更新y的最短路径
            }
        }
    }

    // 最终检查从s到t的最短路径
    if (mindist[t] == INT_MAX)
        cout << "unreachable";  // 如果目标节点t不可达，输出 "unreachable"
    else
        cout << mindist[t];  // 否则，输出从节点s到节点t的最短路径

    return 0;
}