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.从第一个节点出发到最后一个节点的受限路径数