Dijkstra 算法是否需要检查所有顶点？

Question

我最近不得不看一看 Dijkstra 算法，它就是证明。

算法的证明在我能找到的所有来源中终止，所有顶点的数量和访问的所有顶点的数量相等（例如 R=V 或 S=V）。此外，当 Q（以图的所有顶点开始）为空时，该算法的 while 循环终止，因此必须访问所有顶点。

我不明白为什么必须如此。是否存在算法不必访问所有顶点的图，例如：起始顶点直接连接到权重为 1 的“查找”顶点和权重为 10 的其他顶点。

我希望你能解决我在这里遇到的问题。

编辑：这是我从 Cormen 使用的伪代码：

Answer 1

默认形式的 Dijkstra 算法计算从起始节点到所有连接节点的最短距离。即使在这种形式中，它也不会访问所有节点：只需要检查连接组件的顶点。

对于两个节点之间的最短路径，有一个更有效的版本，一旦所有可能的路径都比目前找到的最短路径更长，它就会停止。这个版本并不总是访问连接子图的所有节点。