时间戳

首页 > 解决方案 > 为什么在 Dijkstra 算法中使用 PriorityQueue？

algorithm - 为什么在 Dijkstra 算法中使用 PriorityQueue？

问题描述

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

访问一个顶点后，为什么我们必须将相邻顶点存储到 PriorityQueue 而不是普通 Queue ？

我问上述问题的原因是：我了解 PriorityQueue 我们可以从队列中获取最大/最小数字。但是在 Dijkstra 算法的情况下，我们无论如何都会访问所有顶点，而不管距离/优先级如何。在这种情况下，为什么我们需要使用复杂度为 O(log N) 的 PriorityQueue ，而普通队列会做 O(1) ？

我错过了什么吗？

标签： algorithmdata-structurespriority-queueshortest-pathdijkstra

解决方案

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 是错误的。使用优先级队列肯定是正确的。

推荐阅读