为何自定义比较器的std::priority_queue在Dijkstra实现中排序异常？

这不是std::priority_queue的异常行为，而是它的设计特性——堆结构的维护仅在元素插入（push）、弹出（pop）等修改队列的操作时触发，不会因为外部依赖的变量变化自动重构整个堆。

问题具体分析 #

你的优先级队列比较器依赖外部的dist数组，但：

• 初始插入索引2时，dist[2]是INT_MAX，它在堆中的位置符合当时的优先级规则。
• 当你修改dist[0]为0并插入新的索引0时，新元素会按照当前dist值被正确插入到堆的对应位置，但队列中已有的元素（比如索引2）不会因为dist的变化被重新评估优先级——priority_queue没有机制监控外部状态的改变，也不会自动重新调整堆结构。
• 此时堆顶的索引2其实是无效条目（它对应的dist[2]还是INT_MAX，不是当前的最小距离），但队列不会主动清理它，直到你尝试弹出它时，堆才会重新调整结构。

解决方案 #

Dijkstra算法中常用的应对方式是延迟删除：允许队列中存在重复索引，在处理堆顶元素时先检查它是否是有效的（即该索引对应的dist值是否是已知的最小距离），如果无效就直接跳过。

修改你的代码逻辑，跳过无效的堆顶元素后，断言就能通过：

// 跳过所有无效的堆顶条目
while (!q.empty() && dist[q.top()] == INT_MAX) {
    q.pop();
}
assert(q.top() == 0); // 现在断言会成功

如果想要避免重复元素，可以使用std::set替代priority_queue，因为set会自动维护有序性：

• 存储pair<int, int>（距离+索引），利用set的有序性自动排序。
• 更新距离时，先删除旧的pair（如果存在），再插入新的pair。

注意 #

不要尝试直接修改priority_queue的底层容器来重构堆，这会破坏其封装性，而且不符合标准库的使用规范。

内容的提问来源于stack exchange，提问作者cwa76