未找到具有优先级队列的 Dijkstra 算法处理目的地吗？

Question

我知道算法是如何工作的——但是当使用优先级队列试图找到无法找到的目标节点时，它似乎只会在循环中无休止地反弹。

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

Answer 1

在每次迭代中，从优先级队列中只提取一个节点，并且永远不会再添加。因此，优先级队列最终会变空，当这种情况发生时，算法就会停止。如果没有到目标节点的路径，则无法访问的节点将其前驱指针设置为 nil（这是它们的初始值）。

该算法通常以两种方式之一制定：

• 首先仅将起始节点添加到优先级队列。在这种情况下，当找到所有可达节点时，算法将停止。
• 首先将所有节点添加到优先级队列。在这种情况下，当队列中只剩下不可达节点时，您将开始提取不可达节点，但每个节点都有无穷远的距离，因此它们永远不会为任何其他节点贡献更短的路径。