Dijkstra 算法，如果它不存在路径

Question

我想知道你是否有一个源顶点和一个目标顶点，我想找到它们之间的最短路径。 我的问题是源和目标顶点之间不存在路径然后在 Djikstras 算法中会发生什么，这个算法会发现它吗？

Djikstra's Algorithm

Answer 1

算法最终会 运行 检查可能的路径，确定这是不可能的：到目标顶点的距离仍然是无穷大，因为它被初始化了。

虽然不一定是确定这一点的最佳方法。