小编Ben*_*dio的帖子

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

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

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

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

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