std::priority_queue不支持堆内元素修改，更新距离后需push新节点并跳过过时条目；邻接表推荐vector；Dijkstra不适用于负权边，应改用Bellman-Ford或SPFA。
用 std::priority_queue 实现 Dijkstra 时为什么距离更新后队列不自动排序
因为 std::priority_queue 不支持堆内元素修改，插入后无法调整位置。常见错误是：发现更短距离时直接 push 新节点，却不标记旧节点失效——导致后续重复处理过时的高代价路径。
- 必须配合一个
dist[] 数组实时记录当前已知最短距离
- 每次从堆中
pop 出节点时，先检查 dist[u] != 当前弹出的距离，若不等说明已过时，直接跳过
- 不要尝试用
make_heap 手动重排队列——开销大且易错
邻接表建图该用 vector> 还是 vector>>
推荐后者：vector>> graph(n)，其中 graph[u] 存储所有从 u 出发的边，pair 表示 {v, weight}（终点与权重）。
- 前者（单个
vector）只能表达全局边集，无法快速枚举某点的邻接点，Dijkstra 中每轮需遍历所有边，时间退化为 O(EV)
- 后者支持
O(degree(u)) 遍历邻居，总复杂度保持 O((V + E) log V)
- 若图稀疏（
E ≈ V），空间也更紧凑；稠密图可考虑邻接矩阵，但仅限 V
遇到负权边就崩？不是说 Dijkstra 不能处理负权吗
是的，标准 Dijkstra 在存在负权边时结果不可靠——它依赖“已确定最短距的节点不会再被更新”这一前提，而负权边会破坏该性质。
- 若你发现算法输出路径比实际长，或
dist[v] 在后期又被更小值覆盖，大概率是输入含负权边
- 此时应换用
Bellman-Ford（支持负权、可检测负环）或 SPFA（Bellman-Ford 的队列优化版）
- 注意：负权环存在时，最短路无定义；Dijkstra 对此完全无感知，也不会报错，只会静默给出错误结果
C++ 完整可运行的 Dijkstra 实现（带注释）
#include
#include
#include
#include
using namespace std;
struct Edge {
int to, w;
};
vector dijkstra(int n, const vector>& graph, int start) {
vector dist(n, LLONG_MAX);
dist[start] = 0;
// 小顶堆：{距离, 节点}
priority_queue, vector>, greater>& 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> 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 是初始化哨兵值，比较时别用
== 判未访问——应统一用
或 > 比较距离大小。图中节点编号从 0 开始是多数竞赛和库的默认习惯，别在索引上 off-by-one。
