Dijkstra
进阶Dijkstra 用贪心策略逐步锁定最短路径，不能处理负权边。
// 算法讲解
Dijkstra
输入节点数、起点和带权边，观察 Dijkstra 的贪心松弛过程。
待机
速度 中
待机 ⌨1vector<long long> dijkstra(int src, vector<vector<pair<int,int>>>& adj) {
2 int n = adj.size();
3 vector<long long> dist(n, LLONG_MAX);
4 priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
5 dist[src] = 0;
6 pq.push({0, src});
7 while (!pq.empty()) {
8 auto [d, u] = pq.top(); pq.pop();
9 if (d > dist[u]) continue;
10 for (auto [v, w] : adj[u]) {
11 if (dist[u] + w < dist[v]) {
12 dist[v] = dist[u] + w;
13 pq.push({dist[v], v});
14 }
15 }
16 }
17 return dist;
18}
复杂度分析
时间 O((V+E) log V)
空间 O(V)
最优 O(V log V) 稀疏图
最坏 O((V+E) log V)
算法讲解
Dijkstra 算法维护一个距离数组 dist[]，初始时起点为 0，其余为无穷大。
每轮从所有未确定节点中选出 dist 最小的，标记为已确定，然后用它的出边松弛邻居的距离。
用优先队列优化后，每次取最小 dist 的时间为 O(log V)，总复杂度为 O((V+E) log V)。
它不能处理负权边，因为贪心假设"当前最近的不会再被更新"在负权下不成立。