Dijkstra的算法为什么一定要先扩展当前代价最小的节点？

Question

我在其他帖子上看到，Dijkstra算法总是先展开最短路径。为什么一定要这样实施呢？假设我们创建了 Dijkstra 的轻松版本，它扩展了 any unvisited paths/nodes 只要它们的成本（在上一次迭代中计算）小于无穷大。

我已经完成了一些示例，但尚未展示无法使用此宽松版本的算法计算正确的最短路径的示例。

Answer 1

如果你扩展任何节点，你最终会找到一些通往目标的路径，但你不能保证到目标的路径成本是最优的。

如果您找到到已访问节点的更便宜的路径，则必须从该已访问节点传递地更新所有节点，从而使您的宽松算法的效率低于原始算法。