std::priority_queue不支持堆内元素修改，更新距离后需push新节点并跳过过时条目；邻接表推荐vector；Dijkstra不适用于负权边，应改用Bellman-Ford或SPFA。
用 std::priority_queue 实现 Dijkstra 时为什么距离更新后队列不自动排序
因为 std::priority_queue 不支持堆内元素修改，插入后无法调整位置。常见错误是：发现更短距离时直接 push 新节点，却不标记旧节点失效——导致后续重复处理过时的高代价路径。
- 必须配合一个
dist[]数组实时记录当前已知最短距离 - 每次从堆中
pop出节点时，先检查dist[u] != 当前弹出的距离，若不等说明已过时，直接跳过 - 不要尝试用
make_heap手动重排队列——开销大且易错
邻接表建图该用 vector<pair int>></pair> 还是 vector<vector int>>></vector>
推荐后者：vector<vector int>>> graph(n)</vector>，其中 graph[u] 存储所有从 u 出发的边，pair<int int></int> 表示 {v, weight}（终点与权重）。
- 前者（单个
vector<pair></pair>）只能表达全局边集，无法快速枚举某点的邻接点，Dijkstra 中每轮需遍历所有边，时间退化为O(EV) - 后者支持
O(degree(u))遍历邻居，总复杂度保持O((V + E) log V) - 若图稀疏（
E ≈ V），空间也更紧凑；稠密图可考虑邻接矩阵，但仅限V
遇到负权边就崩？不是说 Dijkstra 不能处理负权吗
是的，标准 Dijkstra 在存在负权边时结果不可靠——它依赖“已确定最短距的节点不会再被更新”这一前提，而负权边会破坏该性质。
Blog for Agents for Knowledge Sharing
下载
在 AgentBlog（blog.agentloka.ai）上作为已认证 AI 代理发布博客文章，支持发布、编辑、删除、评论、浏览和阅读长篇内容。
- 若你发现算法输出路径比实际长，或
dist[v]在后期又被更小值覆盖，大概率是输入含负权边 - 此时应换用
Bellman-Ford（支持负权、可检测负环）或SPFA（Bellman-Ford 的队列优化版） - 注意：负权环存在时，最短路无定义；Dijkstra 对此完全无感知，也不会报错，只会静默给出错误结果
C++ 完整可运行的 Dijkstra 实现（带注释）
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
struct Edge {
int to, w;
};
vector<long long> dijkstra(int n, const vector<vector<Edge>>& graph, int start) {
vector<long long> dist(n, LLONG_MAX);
dist[start] = 0;
// 小顶堆：{距离, 节点}
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>& pq;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // 过时条目，跳过
for (auto& e : graph[u]) {
int v = e.to;
long long new_dist = dist[u] + e.w;
if (new_dist < dist[v]) {
dist[v] = new_dist;
pq.push({new_dist, v});
}
}
}
return dist;
}
int main() {
int n = 4, m = 5, s = 0;
vector<vector<Edge>> graph(n);
// 添加边：u->v 权重 w
graph[0].push_back({1, 1});
graph[0].push_back({2, 4});
graph[1].push_back({2, 2});
graph[1].push_back({3, 6});
graph[2].push_back({3, 3});
auto res = dijkstra(n, graph, s);
for (int i = 0; i < n; ++i)
cout << "dist[" << i << "] = " << res[i] << "\n";
}
注意 dist 类型用 long long 防止松弛时溢出；LLONG_MAX 是初始化哨兵值，比较时别用 == 判未访问——应统一用 或 <code>> 比较距离大小。图中节点编号从 0 开始是多数竞赛和库的默认习惯，别在索引上 off-by-one。
立即学习“C++免费学习笔记（深入）”；
