本课时有配套视频讲解，购买后即可观看（永久有效）

Dijkstra堆优化求单源最短路径

一、课上练习

编程练习

（暂无）

二、知识总结

✨ 核心思想

朴素 Dijkstra 每次要遍历所有顶点来找最小距离，时间为 $O(V^2)$ 。当图是稀疏图（ $E \ll V^2$ ）时，可以用**优先队列（小根堆）**来加速"找最小距离顶点"的操作，将时间复杂度优化为 $O(E \log V)$ 。

这就是 Dijkstra 的堆优化版本，也是竞赛中最常用的最短路算法。

✨ 算法原理

堆优化的核心改进：

用小根堆（priority_queue）维护 (dist[v], v) 对，堆顶始终是距离最小的未确定顶点。
每次从堆顶取出距离最小的顶点 $u$ $u$ ：
- 如果 $u$ 已确定（vis[u] = true），跳过。
- 否则确定 $u$ ，遍历其所有邻边进行松弛。
松弛成功时，将新的 (dist[v], v) 入堆。

注意：由于 C++ 的 priority_queue 默认是大根堆，我们需要存负距离或使用 greater<> 使其变为小根堆。

堆中可能存在同一顶点的多个过时条目（"懒删除"），通过 vis 数组跳过即可。

✨ 代码实现

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 200005;
5const long long INF = 1e18;
6
7vector<pair<int, int>> adj[MAXN]; // 邻接表：adj[u] = {(v, w)}
8long long dist[MAXN];             // 最短距离
9bool vis[MAXN];                   // 是否已确定
10int n, m, s;
11
12void dijkstra(int s) {
13    // 初始化
14    for (int i = 1; i <= n; i++) {
15        dist[i] = INF;
16        vis[i] = false;
17    }
18    dist[s] = 0;
19
20    // 小根堆：{距离, 顶点编号}
21    priority_queue<pair<long long, int>,
22                   vector<pair<long long, int>>,
23                   greater<pair<long long, int>>> pq;
24    pq.push({0, s});
25
26    while (!pq.empty()) {
27        auto [d, u] = pq.top();
28        pq.pop();
29
30        // 如果已确定，跳过（懒删除）
31        if (vis[u]) continue;
32        vis[u] = true;
33
34        // 松弛所有邻边
35        for (auto [v, w] : adj[u]) {
36            if (!vis[v] && dist[u] + w < dist[v]) {
37                dist[v] = dist[u] + w;
38                pq.push({dist[v], v});
39            }
40        }
41    }
42}
43
44int main() {
45    ios::sync_with_stdio(false);
46    cin.tie(nullptr);
47
48    cin >> n >> m >> s;
49    for (int i = 0; i < m; i++) {
50        int u, v, w;
51        cin >> u >> v >> w;
52        adj[u].push_back({v, w});
53    }
54
55    dijkstra(s);
56
57    for (int i = 1; i <= n; i++) {
58        if (dist[i] == INF)
59            cout << -1;
60        else
61            cout << dist[i];
62        if (i < n) cout << " ";
63    }
64    cout << endl;
65
66    return 0;
67}

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 200005;
5const long long INF = 1e18;
6
7vector<pair<int, int>> adj[MAXN];
8long long dist[MAXN];
9bool vis[MAXN];
10int pre[MAXN]; // 记录前驱节点，用于还原路径
11int n, m, s;
12
13void dijkstra(int s) {
14    for (int i = 1; i <= n; i++) {
15        dist[i] = INF;
16        vis[i] = false;
17        pre[i] = -1;
18    }
19    dist[s] = 0;
20
21    priority_queue<pair<long long, int>,
22                   vector<pair<long long, int>>,
23                   greater<>> pq;
24    pq.push({0, s});
25
26    while (!pq.empty()) {
27        auto [d, u] = pq.top();
28        pq.pop();
29        if (vis[u]) continue;
30        vis[u] = true;
31
32        for (auto [v, w] : adj[u]) {
33            if (!vis[v] && dist[u] + w < dist[v]) {
34                dist[v] = dist[u] + w;
35                pre[v] = u; // 记录前驱
36                pq.push({dist[v], v});
37            }
38        }
39    }
40}
41
42// 输出从s到t的最短路径
43void printPath(int t) {
44    if (pre[t] == -1) {
45        cout << t;
46        return;
47    }
48    printPath(pre[t]);
49    cout << " -> " << t;
50}

✨ 执行示例

图：5 个顶点，源点 $s = 1$ 。

边：1→2(2), 1→3(5), 2→3(1), 2→4(6), 3→4(3), 3→5(8), 4→5(2)

堆的变化过程：

步骤	堆顶 (dist, u)	操作	堆中内容
初始	-	push(0,1)	{(0,1)}
1	(0,1)	确定1，松弛2和3	{(2,2), (5,3)}
2	(2,2)	确定2，松弛3和4	{(3,3), (5,3), (8,4)}
3	(3,3)	确定3，松弛4和5	{(5,3), (6,4), (8,4), (11,5)}
4	(5,3)	3已确定，跳过	{(6,4), (8,4), (11,5)}
5	(6,4)	确定4，松弛5	{(8,4), (8,5), (11,5)}
6	(8,4)	4已确定，跳过	{(8,5), (11,5)}
7	(8,5)	确定5	{(11,5)}
8	(11,5)	5已确定，跳过	{}

最终结果：dist = [0, 2, 3, 6, 8]。

✨ 解题步骤详解

建图：用邻接表存储，注意有向/无向。
选择版本：
- $V \leq 5000$ ，稠密图 → 朴素 $O(V^2)$ 。
- $V$ 较大，稀疏图 → 堆优化 $O(E \log V)$ 。
注意数据范围：
- 边权和可能超 int，dist 用 long long。
- 堆中存 long long 与 int 的 pair。
输出路径：若需要，用 pre[] 数组记录前驱，递归或栈输出。

堆优化 vs 朴素版对比：

	朴素版	堆优化版
找最小值	$O(V)$ 遍历	$O(\log V)$ 堆操作
总复杂度	$O(V^2)$	$O(E \log V)$
稠密图	更优	常数较大
稀疏图	太慢	更优

✨ 常见错误

大根堆误用：C++ 的 priority_queue 默认是大根堆，必须加 greater<> 参数或存负值。
不使用 vis 数组：堆中可能有过时条目，不检查 vis 会导致重复处理和错误。
dist 使用 int 溢出：多条边的权值累加可能超过 int，应使用 long long。
堆中存储过时距离后未正确跳过：取出堆顶后必须检查 vis[u]。
邻接表开小：MAXN 要足够大，注意顶点编号范围。
无向图只加单向边：无向图每条边要加两次。

✨ 算法评价

指标	分析
时间复杂度	$O(E \log V)$ ，堆操作最多 $O(E)$ 次
空间复杂度	$O(V + E)$ ，邻接表 + 堆
适用条件	边权非负的稀疏图
竞赛地位	最常用的单源最短路算法
实现难度	简单，模板固定

堆优化 Dijkstra 是竞赛选手必须熟练掌握的基础模板，能处理绝大多数非负权图的最短路问题。

三、课后练习

编程练习

城市路：T1381