为何实现Dijkstra算法时Java Priority Queue执行后未为空？

我之前踩过一模一样的坑，其实这是Java PriorityQueue 实现Dijkstra时的常见现象，咱们慢慢捋清楚：

核心原因：PriorityQueue不会自动清理旧条目 #

在Dijkstra的常规实现逻辑里，当你更新某个节点的最短距离后，会把这个节点（带着新的最短距离）再次加入队列，但队列里之前存在的、带着更大距离（比如初始的Infinity）的同节点条目，并不会被自动移除或更新。这些旧条目会一直留在队列里，直到被取出——而当你取出它们时，会发现它们记录的距离已经不是当前节点的最短距离了，这时候你会直接跳过处理这些无效条目。

所以你的程序能生成正确结果，恰恰说明你已经正确处理了这些旧条目，只是它们还没被取出来，留在队列里而已。

验证你的处理逻辑 #

你可以检查下取出队列元素的代码，应该有类似这样的判断：

while (!priorityQueue.isEmpty()) {
    Node current = priorityQueue.poll();
    // 如果当前条目记录的距离已经不是节点的最短距离，直接跳过
    if (current.distance > shortestDistance[current.id]) {
        continue;
    }
    // 处理邻居节点、更新距离的逻辑...
}

如果你的代码里有这个continue判断，那队列里剩下的那些Infinity条目就是还没被poll到的旧条目，完全不影响结果的正确性。

要不要特意清空队列？ #

其实完全没必要。当算法结束时，所有可达节点的最短路径都已经确定，队列里剩下的要么是不可达的节点（距离始终是Infinity），要么是已经被跳过的旧条目，它们不会对最终结果造成任何影响。强行循环取出所有元素清空队列，反而会浪费不必要的性能。

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