代码随想录算法训练营第五十九天 | 图论part09

使用邻接表和堆来优化dijkstra算法。原来的时间复杂度是$O(n^2)$，n是节点数量。
使用堆优化，从宏观角度来说就是将每条边都加入堆，一共是E条边，每次操作的时间复杂度是$log(E)$，所以时间复杂度是$Elog(E)$。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <list>
#include <fstream>
#include <climits>using namespace std;struct Edge {int end, val;Edge(int end, int val):end(end), val(val) {}
};class myCompare {
public:bool operator()(const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;}
};int main() {int n, m;int s, e, v;ifstream infile("input.txt");cin >> n >> m;vector<list<Edge>> graph(n + 1);while (m--) {cin >> s >> e >> v;graph[s].emplace_back(Edge(e, v));}// 记录访问的一维数组vector<bool> visited(n + 1, false);// 记录到源点的距离的一维数组  vector<int> minDist(n + 1, INT_MAX);// 记录目前已知到源点距离最短的点和距离priority_queue <pair<int, int>, vector<pair<int, int>>, myCompare> pq;minDist[1] = 0;pq.push({ 1, 0 });while (!pq.empty()) {// 找到距离源点最近的节点pair<int, int> cur = pq.top(); pq.pop();if (visited[cur.first]) continue;// 将节点标记为已访问visited[cur.first] = true;// 更新非访问节点的minDistfor (Edge edge : graph[cur.first]) {if (!visited[edge.end] && edge.val + cur.second < minDist[edge.end]) {minDist[edge.end] = edge.val + cur.second;pq.push({ edge.end, minDist[edge.end] });}}}if (minDist[n] == INT_MAX) cout << -1 << endl;else cout << minDist[n] << endl;return 0;
}

Bellman_ford算法就是松弛n-1次。每一次会将所有点到源点的距离更新。

使用Bellman_ford算法，需要以下数据结构：

• 邻接表
• 记录到源点的距离的一维数组

#include <iostream>
#include <vector>
#include <list>
#include <fstream>
#include <climits>using namespace std;struct Edge {int from, end, val;Edge(int from, int end, int val):from(from), end(end), val(val) {}
};int main() {int n, m;int s, e, v;ifstream infile("input.txt");cin >> n >> m;vector<Edge> graph;while (m--) {cin >> s >> e >> v;graph.emplace_back(Edge(s, e, v));}// 记录到源点的距离的一维数组  vector<int> minDist(n + 1, INT_MAX);minDist[1] = 0;for (int i = 1; i < n; ++i) { // 重复n-1次for (Edge& e : graph) {if (minDist[e.from] != INT_MAX && minDist[e.end] > minDist[e.from] + e.val) {minDist[e.end] = minDist[e.from] + e.val;}}}if (minDist[n] == INT_MAX) cout << "unconnected" << endl;else cout << minDist[n] << endl;return 0;
}