c++如何实现迪杰斯特拉最短路径算法_c++ 优先队列优化与邻接表【详解】_技术教程

Dijkstra必须用priority_queue配合邻接表以达O((V+E)log V)复杂度；优先队列保证取最小距离节点为O(log V)，邻接表确保只遍历真实存在的边；需接受重复入队并跳过过期节点。

为什么 `dijkstra` 一定要用 `priority_queue` 配合邻接表？

不用优先队列的朴素 dijkstra 时间复杂度是 O(V²)，对点数超 10⁴ 的图基本不可用；而用 std::priority_queue + 邻接表可压到 O((V+E) log V)。关键在于：每次取最小距离节点必须是 O(log V)，且只遍历真实存在的边（邻接表保证 E 级别访问），不是全扫数组。

常见错误是把 priority_queue 当成“自动更新堆顶”的容器——它不支持修改已有元素的值，所以必须接受重复入队：当发现更短路径时，直接 push 新二元组 {dist, node}，旧的会在后续被 pop 时跳过（靠 if (dist[node] 过滤）。

`priority_queue` 的比较规则怎么写才不翻车？

C++ 默认是大根堆，但我们要的是“距离最小的先出”，所以必须自定义比较器。最稳妥写法是用仿函数或 lambda，且注意：不能直接写 greater>，因为 pair 比较先比 first，而我们希望 first 是距离，所以要让小距离排前面——即“less”语义，但 priority_queue 的模板参数是“谁该被优先弹出”，所以实际要传入「大于」逻辑（即当 a > b 时，a 应该后出，b 先出）。

推荐写法：
```
priority_queue, vector>, greater>> pq;
```

等价但更清晰的 lambda 写法（C++11+）：

auto cmp = [](const pair& a, const pair& b) { return a.first > b.first; };
priority_queue, vector>, decltype(cmp)> pq(cmp);

错误示范：priority_queue>（大根堆，会先弹出最大距离）

邻接表怎么建？`vector>>` 还是 `vector>`？

用 vector>> 是最常用且高效的选择：第一维是起点编号，第二维每个 pair 表示一条有向边（无向图就双向加）。它缓存友好、随机访问快、构造简单。除非边数极少且频繁删边，否则别用 list 或 map。

注意权重类型：如果题目给的是非负整数，用 int；若可能超 INT_MAX 或含浮点，需统一换成 long long 或 double，并同步改 dist 数组和 priority_queue 中的类型。

建边示例（无向图）：

vector>> graph(n);
// 加边 u->v 权重 w
graph[u].emplace_back(v, w);
graph[v].emplace_back(u, w);

初始化、松弛、跳过失效节点这三步最容易漏哪？

三个关键动作必须严格按序，缺一不可：

初始化：dist 数组全设为 INT_MAX（或 LLONG_MAX），dist[src] = 0，然后 pq.push({0, src})
松弛：对当前节点 u 的每条出边 (u→v, w)，若 dist[u] + w ，则更新 dist[v] 并 pq.push({dist[v], v})
跳过失效节点：在 while (!pq.empty()) 循环开头，auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; —— 这行不能省，否则会处理过期状态，导致结果错误或超时