代码随想录算法训练营第五十九天 | 图论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;

		// 更新非访问节点的minDist
		for (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;
}