2026/6/7/周日下午三人笔记(Dij优先队列优化)
堆优化 Dijkstra 算法笔记
适合学完优先队列、图的邻接表后复习使用。
核心用途：求 非负边权图 中，从一个起点到其他所有点的最短路。
一、代码模板
先直接看完整模板。
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int to; // 边的终点
long long weight; // 边权
};
struct Node {
long long dist; // 当前从起点到这个点的距离
int id; // 点的编号
};
// 小根堆：距离更小的点优先出队
bool cmp(Node a, Node b) {
return a.dist > b.dist;
}
const int N = 1000005;
const long long INF = 1e18;
int n, m, startNode;
vector<Edge> graph[N]; // 邻接表存图
long long dist[N]; // dist[i] 表示起点到 i 的最短距离
bool visited[N]; // visited[i] 表示 i 是否已经确定最短路
priority_queue<Node, vector<Node>, decltype(&cmp)> pq(cmp);
int main() {
cin >> n >> m >> startNode;
// 读入有向图：x -> y，边权为 z
for (int i = 1; i <= m; i++) {
int x, y;
long long z;
cin >> x >> y >> z;
graph[x].push_back({y, z});
}
// 初始化所有距离为无穷大
for (int i = 1; i <= n; i++) {
dist[i] = INF;
}
// 起点到自己的距离为 0
dist[startNode] = 0;
pq.push({0, startNode});
// 堆优化 Dijkstra
while (!pq.empty()) {
Node current = pq.top();
pq.pop();
int u = current.id;
// 如果这个点已经确定过最短路，就跳过
if (visited[u]) {
continue;
}
visited[u] = true;
// 用当前点 u 去更新它能到达的点
for (Edge edge : graph[u]) {
int v = edge.to;
long long w = edge.weight;
// 松弛操作：如果经过 u 到 v 更短，就更新 dist[v]
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
// 输出起点到每个点的最短距离
for (int i = 1; i <= n; i++) {
cout << dist[i] << ' ';
}
return 0;
}
二、这个算法解决什么问题？
Dijkstra 算法用来解决：
给定一个带边权的图，求从一个起点到其他所有点的最短距离。
常见输入形式：
n m s
x1 y1 z1
x2 y2 z2
...
xm ym zm
含义：
n：点数m：边数s：起点x y z：从x到y有一条边，长度是z
如果是无向图，需要存两条边：
graph[x].push_back({y, z});
graph[y].push_back({x, z});
如果是有向图，只存一条边：
graph[x].push_back({y, z});
三、什么时候可以用 Dijkstra？
Dijkstra 适用于：
- 单源最短路
- 边权非负
- 图可以是有向图，也可以是无向图
不能用于：
- 有负边权的图
- 需要处理负环的图
如果边权可能为负，通常要考虑 Bellman-Ford 或 SPFA。
四、核心思想
Dijkstra 的核心思想是：
每次从还没确定最短路的点中，找出当前距离起点最近的点。
这个点的最短路就可以确定了。
然后用这个点去更新它周围的点。
这个更新过程叫做 松弛。
五、几个重要数组和结构体
1. 邻接表 graph
vector<Edge> graph[N];
表示一张图。
如果有一条边：
1 -> 3，边权为 5
就存成：
graph[1].push_back({3, 5});
2. 距离数组 dist
long long dist[N];
含义：
dist[i] = 起点到 i 的当前最短距离
初始化时：
dist[i] = INF;
起点：
dist[startNode] = 0;
3. 标记数组 visited
bool visited[N];
含义：
visited[i] = true;
表示点 i 的最短路已经确定，不需要再处理。
4. 优先队列 pq
priority_queue<Node, vector<Node>, decltype(&cmp)> pq(cmp);
作用：
每次快速取出当前距离起点最近的点。
因为 C++ 默认的 priority_queue 是大根堆，所以要写比较函数，让它变成小根堆。
bool cmp(Node a, Node b) {
return a.dist > b.dist;
}
这里的意思是：
dist小的优先级更高。
六、松弛操作
松弛是 Dijkstra 最重要的操作。
如果现在已经知道：
dist[u]
表示起点到 u 的最短距离。
又有一条边：
u -> v，边权为 w
那么从起点到 v 可以尝试走：
起点 -> u -> v
距离就是：
dist[u] + w
如果这个距离比原来的 dist[v] 更小，就更新：
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
这就是松弛。
七、算法流程
- 建图。
- 所有距离初始化为
INF。 - 起点距离设为
0。 - 把起点放入优先队列。
- 每次取出距离最小的点
u。 - 如果
u已经处理过，跳过。 - 否则标记
u已确定最短路。 - 用
u更新所有邻接点。 - 队列为空时，算法结束。
八、正确性证明
1. 要证明什么？
我们要证明：
当一个点
u第一次从优先队列中取出并被标记visited[u] = true时，dist[u]就是起点到u的最短距离。
2. 为什么当前取出的点一定最短？
优先队列每次取出的是当前 dist 最小的点。
假设当前取出的点是 u。
如果存在一条更短的路径能到达 u，那么这条路径一定要经过某个还没有确定的点。
但是由于所有边权都是非负数：
路径继续往后走，距离只会变大，不会变小。
所以一个还没确定的点，不可能绕一圈后得到比当前 dist[u] 更小的距离。
因此，当前 u 的距离已经不可能再变小。
所以：
dist[u]
就是起点到 u 的最短路。
3. 为什么边权不能为负？
如果有负边，后面可能出现：
先走一段比较长的路，再通过负边把总距离变小
这样一个已经被确定的点，之后可能又被更新得更小。
这会破坏 Dijkstra 的正确性。
所以 Dijkstra 要求：
所有边权必须非负。
九、时间复杂度分析
设：
n是点数m是边数
使用邻接表存图。
每条边最多被检查一次或少数几次。
每次更新距离时，会向优先队列中插入一个新状态。
优先队列每次 push 或 pop 的复杂度是：
O(log m)
所以总时间复杂度通常写作：
O((n + m) log m)
也常写成：
O(m log m)
或：
O(m log n)
空间复杂度：
O(n + m)
原因：
- 邻接表存边：
O(m) - 距离数组、标记数组：
O(n) - 优先队列：最多存若干个待处理状态
十、常见题型
题型 1：有向图单源最短路
题意：
给出有向边，求从起点到所有点的最短距离。
建图：
graph[x].push_back({y, z});
只存一条边。
题型 2：无向图单源最短路
题意：
道路可以双向通行，求从起点到所有点的最短距离。
建图：
graph[x].push_back({y, z});
graph[y].push_back({x, z});
要存两条边。
题型 3：求起点到终点的最短路
有些题不要求输出所有点，只要求输出起点到终点的距离。
假设终点是 target。
最后输出：
cout << dist[target];
也可以在终点第一次出队时提前结束：
if (u == target) {
break;
}
因为 Dijkstra 中，一个点第一次被确定时，它的最短路已经确定。
题型 4：无法到达的点
如果算法结束后：
dist[i] == INF
说明起点到 i 不可达。
可以按题目要求输出：
if (dist[i] == INF) {
cout << -1 << ' ';
} else {
cout << dist[i] << ' ';
}
题型 5：网格图最短路
如果每个格子有代价，或者从一个格子走到另一个格子的代价不同，也可以用 Dijkstra。
例如：
从 (x, y) 走到 (nx, ny) 的代价是 cost[nx][ny]
松弛可以写成：
if (dist[x][y] + cost[nx][ny] < dist[nx][ny]) {
dist[nx][ny] = dist[x][y] + cost[nx][ny];
pq.push({dist[nx][ny], id(nx, ny)});
}
如果每一步代价都相同，一般用 BFS 更简单。
如果每一步代价不同且非负，可以考虑 Dijkstra。
十一、常见错误
1. 忘记初始化距离
错误：
dist[startNode] = 0;
但是其他点没有设成无穷大。
正确：
for (int i = 1; i <= n; i++) {
dist[i] = INF;
}
dist[startNode] = 0;
2. 无向图只存了一条边
如果题目说道路是双向的，要写：
graph[x].push_back({y, z});
graph[y].push_back({x, z});
不能只写一条。
3. int 爆掉
如果边权很大，路径长度可能超过 int。
建议距离数组使用：
long long dist[N];
无穷大写：
const long long INF = 1e18;
4. 优先队列方向写反
默认 priority_queue 是大根堆。
Dijkstra 需要每次取出距离最小的点，所以要小根堆。
可以用比较函数：
bool cmp(Node a, Node b) {
return a.dist > b.dist;
}
也可以用 greater 写法。
5. 没有跳过已经确定的点
由于同一个点可能被多次放进优先队列，所以要写：
if (visited[u]) {
continue;
}
visited[u] = true;
否则可能重复处理，导致效率变差。
十二、另一种更短的优先队列写法
如果不想写结构体比较函数，也可以使用 pair。
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
含义：
{距离, 点编号}
使用方式：
pq.push({0, startNode});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (visited[u]) continue;
visited[u] = true;
for (auto edge : graph[u]) {
int v = edge.to;
long long w = edge.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
这种写法更短，但初学时结构体写法更清晰。
十三、复习重点
请重点记住这几句话：
- Dijkstra 用来求 非负边权图的单源最短路。
dist[i]表示起点到i的当前最短距离。- 优先队列每次取出当前距离最小的点。
- 一个点第一次被确定时，它的最短路就不会再变。
- 松弛操作是：
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
- 堆优化后复杂度约为：
O(m log n)
十四、背诵版核心代码
最后只背这一段核心即可：
dist[startNode] = 0;
pq.push({0, startNode});
while (!pq.empty()) {
Node current = pq.top();
pq.pop();
int u = current.id;
if (visited[u]) continue;
visited[u] = true;
for (Edge edge : graph[u]) {
int v = edge.to;
long long w = edge.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}