Dijkstra的最短路径算法如何与优先级队列一起工作？

Question

我一直在阅读在线网站，每个人都说使用优先级队列会使它很好，但我不明白在这里用作“优先级”的是什么。

一开始，优先队列上的第一项始终是起点节点吗？如果是这样，当我们用距离0提取起始节点时，我们如何从优先级队列中获取它的邻居？

Answer 1

优先队列Q存储一组不同的元素。每个元素 x都有一个关联的密钥x.key

当Dijkstra基于优先级队列。然后，我们将顶点存储在与源的距离尚未确定的队列中，并键入它们与源的当前距离。

看看这个pdf，其中算法是基于抽象数据结构称为优先级队列，可以使用二进制堆实现。

http://www.cs.bris.ac.uk/~montanar/teaching/dsa/dijkstra-handout.pdf

Answer 2

当实现Dijkstra算法，您可以使用优先级队列，以确定您的访问节点的顺序。

优先级队列包含所有未访问的节点，并允许您删除（然后处理）具有最小指定距离的节点。

优先级队列是非常重要的，因为它确保节点永远不会被访问，直到其分配的距离是准确的，并且其已知的最短路径实际上是最短路径。这意味着你永远不必访问和处理任何节点两次！

但是，请注意，Dijkstra算法可能在访问之前多次减少节点的指定距离。这意味着优先队列必须支持动态增加节点的优先级。 Java和C++提供的标准优先级队列不支持这种操作，不能用于Dijkstra算法。相反，您应该使用ArrayList或std :: vector中的堆来实现自己的优先级队列。