一、图论问题 Ⅷ

1、dijkstra算法 堆优化

采用堆来优化，适合节点多的稀疏图。代码如下：

# include<iostream>
# include<vector>
# include<list>
# include<queue>
# include<climits>

using namespace std;

class mycomparison {
public:
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
        return lhs.second > rhs.second;
    }
};

int main(){
    int n, m;
    cin >> n >> m;
    int s, e, v;
    vector<list<pair<int, int>>> grid(n+1);
    for(int i=0; i<m; ++i){
        cin >> s >> e >> v;
        grid[s].push_back(pair<int, int>(e, v));
    }
    vector<int> minDist(n+1, INT_MAX);
    vector<bool> visited(n+1, false);
    int start = 1, end = n;
    minDist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;
    pq.push(pair<int, int>(start, 0));
    while(!pq.empty()){
        // 1、选取源点到未被访问过且距离最近的节点； 
        auto cur = pq.top(); pq.pop();
        if(visited[cur.first])
            continue;
        // 2、将最近节点标记为访问过 
        visited[cur.first] = true;
        // 3、更新非访问节点到源点的距离
        for(auto edge : grid[cur.first]){
            if(!visited[edge.first] && minDist[edge.first] > minDist[cur.first] + edge.second )
                minDist[edge.first] = minDist[cur.first] + edge.second;
                pq.push(pair<int, int>(edge.first, minDist[edge.first]));
        }
    }
    if(minDist[end] < INT_MAX)
        cout << minDist[end] << endl;
    else
        cout << -1 << endl;

    return 0;
}

2、Bellman_ford 算法

权值有负值的图无法采用dijdijkstra算法，这时需要使用Bellman_ford 算法来解决最短路问题。

#include <iostream>
#include <vector>
#include <list>
#include <climits>

using namespace std;

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

    vector<vector<int>> grid;
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid.push_back({p1, p2, val});
    }
    int start = 1, end = n;  

    vector<int> minDist(n + 1 , INT_MAX);
    minDist[start] = 0;
    for (int i = 1; i < n; i++) { // 对所有边 松弛 n-1 次
        for (vector<int> &side : grid) { // 每一次松弛，都是对所有边进行松弛
            int from = side[0]; // 边的出发点
            int to = side[1]; // 边的到达点
            int price = side[2]; // 边的权值
            // 松弛操作 
            // minDist[from] != INT_MAX 防止从未计算过的节点出发
            if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) { 
                minDist[to] = minDist[from] + price;  
            }
        }
    }
    if (minDist[end] == INT_MAX)
        cout << "unconnected" << endl; // 不能到达终点
    else
        cout << minDist[end] << endl; // 到达终点最短路径
    return 0;
}

参考资料
代码随想录