Dijkstra算法的优先级队列处理目标未找到？

Question

我知道这个算法是如何工作的 - 但是当使用优先级队列试图找到无法找到的目的节点时，它好像会在一个循环中无休止地反弹。

Dijkstra的算法是否处理节点与图断开的情况？

Answer 1

在每次迭代中，只有一个节点从优先级队列中提取，并且永远不会再次添加。因此，优先级队列最终将变为空，并且在发生时停止算法。如果没有到达目标节点的路径，则不可达节点将其前导指针设置为零（这是它们的初始值）。通过增加仅仅是开始节点优先级队列

• 开始：

  算法通常被配制两种方式之一。在这种情况下，当找到所有可到达的节点时，该算法将停止。

• 首先将全部节点添加到优先级队列。在这种情况下，当队列中只剩下不可到达的节点时，您将开始提取无法访问的节点，但它们中的每一个都具有无穷大的距离，因此它们永远不会向其他任何节点贡献较短的路径。

Answer 2

长话短说，也不会无限循环，因为Dijkstra算法是BFS（由水平横向水平）+贪婪（放松从以前的水平，以目前的水平距离），它并没有穿越回到先前level 。该算法将在队列为空时结束。

如果找不到目标，算法应该返回-1或null。