为什么Dijkstra算法中使用PriorityQueue？

Question

我一直试图理解Dijkstra算法的内在原理，以找到加权图的最短路径。

在访问一个顶点后，为什么我们必须将相邻顶点存储到优先级队列而不是普通队列中？

我问上述问题的原因是：我知道使用PriorityQueue，我们可以从队列中获得最大/最小的数字。但是在Dijkstra算法的情况下，我们无论如何都会访问所有的顶点，而不管距离/优先级如何。在这种情况下，为什么我们需要使用具有O（log N）复杂度的PriorityQueue，而正常的Queue将执行O（1）？

我错过什么了吗？

Answer 1

到达顶点可以有多种方式，使用优先级队列可以确保在访问顶点时找到到顶点的最短距离。

考虑以下图表：

 a
 |\
1| \3
 |  \
 c---b
   1  \
       \
       ...

当我们访问顶点a时，我们会将顶点b和顶点c分别放入距离为3和1的优先级队列中。如果我们不使用优先级队列，我们可能会首先访问b，这是一个问题，因为我们目前知道的到b的最短距离是次优的。

如果我们使用优先级队列，我们可以证明，当我们探索一个顶点时，没有一条路径比我们目前知道的距离短。出于矛盾的考虑，假设我们访问一个顶点b，而该顶点的路径较短。让（u，v）成为b较短路径上的一条边，这样u已被访问，而v未被访问。由于访问了u，我们必须将v添加到队列中，并且由于v位于到b的较短路径上，它的距离必须小于到b的距离，这意味着它必须在b之前访问过。因此，我们有一个矛盾，我们知道没有更短的道路可以存在。

Answer 2

Dijkstra算法（以及BFS）的要点是，当一个节点退出优先级队列（或BFS中的FIFO队列）时，它与源节点的距离应该最短，并且该距离将被锁定。这些节点将被标记为已访问，不再进入队列。这就是为什么FIFO队列在BFS中工作得很好，因为每条边的权重是相等的，与源的最短距离是最小的“跳数”。

现在让我们来考虑这个加权图：

       (s)
       / \
     2/   |
     /    |
   (a)    |
    |     |
   3|     |
    |     |
   (b)    |100
    |     |
   2|     |
    |     |
   (c)    |
    \     |
    4\    |
      \  /
      (d)

让我们尝试使用FIFO队列从节点s查找最短路径。

       Push s:           Queue: [s],    Distance: s:0
Pop s, Push a, d:        Queue: [a, d], Distance: s:0, a:2, d:100
Pop a, Push b:           Queue: [d, b], Distance: s:0, a:2, d:100, b:5
Pop d, Push c:           Queue: [b, c], Distance: s:0, a:2, d:100, b:5, c:104
Pop b, No new neighbors, Queue: [c],    Distance: s:0, a:2, d:100, b:5, c:104
Pop c, No new neighbors, Queue: [],     Distance: s:0, a:2, d:100, b:5, c:104

显然，节点c和d是错误的，其中最短的距离是7和11。使用优先级队列肯定是正确的。