了解 Dijkstra 算法

Question

我正在尝试理解 Dijkstra 算法来寻找最短路径。

我已经想到了这个示例，其中顶部表格对应于左下角的图像。

现在，我的问题是我不明白从步骤 1 到步骤 2 的转换：

当我们处于 UX 时，我们可以通过将 X 到 V 的成本（即 2）添加到我们当前的成本（即 1；UX 的成本）来到达 UXV。所以总和是 3，但由于这个比我们已经发现的 2 大，所以我们不改变它。在步骤 1 中，我们有两个选项，它们的成本相同； UXY和UXV，但是为什么算法选择去UXY而不是UXV呢？

提前致谢！

Answer 1

当您有两个或多个选项且成本相同时，选择哪个选项没有任何区别。

在 Dijkstra 算法维基百科文章 中，有一个部分包含用于实现该算法的伪代码。你可以看到伪代码中有一行

u ← vertex in Q with min dist[u]

，这意味着你选择了成本最低的一个选项。当您以相同的成本有更多选择时，您只需选择其中任何一个即可。

对于您的具体示例，这意味着您也可以转到 UXV 而不是 UXY。这可能会导致更多步骤，但算法完成时最终结果是相同的。