最短路径问题之Dijkstra算法

Dijkstra算法

吐槽

今天参加了leetcode周赛,第三题一眼就看出需要使用到一点到多点的最短距离,第一反应就是Dijkstra算法,奈何平时基本没写过几遍Dijkstra算法,模本没整理好,导致手忙脚乱,四处考古,最后压时提交,还是WA…,很烦,所以花时间把Dijkstra算法,完整的写一遍。
后续可能还会把Floyd算法,SPFA算法,Bellman-Ford算法手撕一遍,做到基本图论问题一网打尽。

简介

解决什么问题

一个图中,求一点到其他点的最短距离。PS:如果仅求一个点到另一个点的最短距离一般使用DFS或BFS即可。

适用什么场景

必须保证点与点之间权值(cost)非负。

哪种实现方式

这里使用优先队列数据结构,使用哈希表建图。

复杂度为多少

大致情况:时间复杂度:O(E + nlogn),E是边的数量,n是点的数量。空间复杂度:O(n)。

代码

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

// n节点数,E是边的数量
// 时间复杂度:O(E + nlogn)
vector<int> Dijkstra(int n,vector<vector<int>>& edges,int start){
	unordered_map<int,unordered_map<int,int>> weight;
	unordered_map<int,vector<int>> G;
	for (auto& e : edges){
		G[e[0]].push_back(e[1]);
		G[e[1]].push_back(e[0]);
		weight[e[0]][e[1]] = e[2];
		weight[e[1]][e[0]] = e[2];
	}
	vector<int> dist(n,INT_MAX);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; //first:当前点的dist[i],second当前点 
	unordered_set<int> seen;
	dist[start] = 0;
	pq.push({0,start});
	while (!pq.empty()){
		int dis = pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if (seen.count(cur)) continue;
		seen.insert(cur);
		for (auto& nxt : G[cur]){
			if (dis + weight[cur][nxt] < dist[nxt]){
				dist[nxt] = dis + weight[cur][nxt];
				pq.push({dist[nxt],nxt});
			}
		}
	}
	for (int i = 0;i < n;++i) cout << dist[i] << " ";
	cout << endl;
	return dist;

}

int main(void){
	vector<vector<int>> edges{{1,2,3},{1,3,3},{2,3,1},{1,4,2},{5,2,2},{3,5,1},{5,4,10}};
	int start = 5;
	int n = 6; 
	// 注意:
	// 这里点的数量应该为5,但是由于给出的点下标是从1开始的,
	// 所以多开一个空间,下标为0的结果数组中的值没有任何意义。
	// 如果较真,那么保证输入点的起始值从0开始就可以无须多开空间。
	
	Dijkstra(n,edges,start);
	return 0;
}

附题

LeetCode
5699.从第一个节点出发到最后一个节点的受限路径数

上一篇:循环队列的实现


下一篇:图 - 邻接矩阵广度优先遍历(C语言)