一、圖論問題 Ⅷ

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;elsecout << -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; // 不能到達終點elsecout << minDist[end] << endl; // 到達終點最短路徑return 0;
}

參考資料
代碼隨想錄