想象你是个快递员，手里有张城市地图（带道路长度），现在要找到从仓库到客户家的最短路线。如果每次都用穷举法尝试所有路径，遇到大城市？直接GG！这时候Dijkstra算法就像你的导航系统，能高效锁定最优解。在竞赛中，这种单源最短路径问题（SPT）几乎每年必考，掌握它意味着你能轻松处理交通规划、网络路由等实际问题。
核心概念讲解
贪心+优先队列的完美组合！
- 松弛操作（Relaxation）：如果发现更短的路径，就更新距离。数学表达：
$$d[v] = \min(d[v], d[u] + w(u,v))$$
其中$d$是距离数组，$w(u,v)$是边权。
- 核心思想：
维护一个已确定最短路径的点集$S$和未确定点集$U$
每次从未确定点中选出当前距离最小的点$u$（贪心选择），将其加入$S$
用$u$更新其邻居的距离（松弛操作）
（图示：红色为已确定点，蓝色为待处理点）
C++代码示例
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10, INF = 0x3f3f3f3f;
vector<pair<int, int>> g[N]; // 邻接表：{to, weight}
int dist[N];
void dijkstra(int s) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // 小根堆
fill(dist, dist + N, INF);
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // 剪枝：旧数据跳过
for (auto &[v, w] : g[u]) { // 遍历邻居
if (dist[v] > dist[u] + w) { // 松弛条件
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
}
int main() {
int n, m, s, t;
cin >> n >> m >> s >> t;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w}); // 无向图需双向加边
}
dijkstra(s);
cout << (dist[t] == INF ? -1 : dist[t]) << endl;
return 0;
}
注释亮点：
priority_queue默认是大根堆，用greater<>转小根堆auto [d, u]是C++17结构化赋值，比传统top()+pop()更简洁if (d > dist[u]) continue是经典剪枝，避免重复处理
算法分析
- 时间复杂度：$O((V+E)\log V)$
（$V$是点数，$E$是边数，优先队列每次插入/删除是$\log V$）
空间复杂度：$O(V+E)$（存储图）
适用场景：非负权图的单源最短路径
局限性：负权边会破坏贪心性质（需用Bellman-Ford）
经典例题
题意：求两点间最短路径，注意输出路径（需记录前驱节点）
关键点：用
vector<int> pre[N]记录路径，回溯时从终点倒推
- 进阶：多源最短路径（先跑一次Dijkstra预处理所有点到起点的距离）
推荐练习
P1383 最短路径 （基础版，测试理解）
P4559 [国家集训队]旅行计划 （带约束的最短路径）
CF115D Roads and Libraries （结合最小生成树）
小结
Dijkstra的核心是贪心选择+松弛更新，优先队列让它效率起飞。下篇文章我们聊聊它的升级版——堆优化Dijkstra vs SPFA，准备好迎接负权边的挑战吧！🚀