图论天花板：Dijkstra最短路径算法详解

一、上期回顾 Day30

掌握图论基础、邻接表、拓扑排序，解决任务依赖、有向图判环、课程排序问题。今天学习图论天花板级高频考点：Dijkstra 单源最短路径算法。

---

二、Dijkstra 算法核心概念

1. 解决什么问题

给定带权有向 / 无向图，求一个起点到其他所有点的最短路径。

• 权值：距离、时间、花费
• 适用：边权非负（没有负数权值）

2. 核心思想（贪心）

1. 每次选离起点最近且未访问的点
2. 用这个点松弛（更新）它邻居的距离
3. 标记已访问，不再重复处理
4. 直到所有点处理完毕

---

三、必备数据结构

1. 邻接表：存图（比邻接矩阵高效）

   vector<pair<int, int>> edge[N]; // edge[u] = {v, w} 从u到v，边权w

2. 距离数组 dist []：dist[i]起点到 i 点的最短距离
3. 访问数组 vis []：标记已确定最短路径的点
4. 优先队列（堆）：堆优化，O (E log V)，效率爆炸

---

四、堆优化 Dijkstra 万能模板（必背）

#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; const int N = 10005; vector<pair<int, int>> edge[N]; // 邻接表：to, weight int dist[N]; // 最短距离 bool vis[N]; // 访问标记 int n, m; // 点数，边数 // Dijkstra 堆优化版 void dijkstra(int start) { // 初始化距离为无穷大 fill(dist, dist + N, INT_MAX); fill(vis, vis + N, false); dist[start] = 0; // 优先队列：小根堆（距离最小优先） // pair<int, int>：{距离，节点编号} priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (vis[u]) continue; // 已处理跳过 vis[u] = true; // 遍历所有邻居 for (auto [v, w] : edge[u]) { if (!vis[v] && dist[v] > d + w) { dist[v] = d + w; pq.push({dist[v], v}); } } } } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; edge[u].emplace_back(v, w); // 无向图再加一行 edge[v].emplace_back(u, w); } dijkstra(1); // 从1号点出发 // 输出到所有点的最短距离 for (int i = 1; i <= n; i++) cout << dist[i] << " "; return 0; }

---

五、关键步骤拆解

1. 初始化：起点距离 = 0，其余无穷大
2. 小根堆：每次拿最近点
3. 松弛操作：

   if (dist[v] > dist[u] + w) dist[v] = dist[u] + w;

4. 标记访问：每个点只处理一次，保证效率

---

六、适用场景

1. 地图导航最短路径
2. 网络传输最小延迟
3. 工程最小花费
4. 带权图单源最短路（无负权）

---

七、易错点提醒

1. 必须用小根堆（greater），不能用默认大根堆
2. 边权不能为负数，否则失效
3. 无向图 = 双向加边
4. 距离数组初始化为极大值

---

八、今日核心总结

1. Dijkstra =贪心 + 堆优化 + 松弛操作
2. 解决带权图单源最短路径
3. 邻接表存图，小根堆提速
4. 时间复杂度O(E log V)，刷题首选
5. 边权不能为负

---

九、课后练习

1. 手写堆优化 Dijkstra 模板
2. 构造简单带权图，求起点到各点最短路
3. 尝试无向图写法