理解Dijkstra算法

Question

我试着理解Dijkstra算法来寻找最短的路径。

我看了这个例子，上面的表对应于左下角的图像。

​

​

现在，我的问题是，我不理解从步骤1到步骤2的过渡：

当我们在UX时，我们可以通过将X到V(这是2)的成本加到我们当前的成本(即1；UX的成本)。所以，之和是3，但由于这个，我比我们已经找到的2大，所以我们不会改变它。在第一步中，我们有两个选择，它们都有相同的成本: UXY和UXV，但是为什么算法选择选择UXY而不是UXV呢？

提前感谢！

Answer 1

当您有两个或多个具有相同成本的选项时，您所使用的选项没有任何区别。

在Dijkstra算法维基百科文章中有一个具有伪码的部分来实现该算法。您可以看到，在伪代码中有一行u ← vertex in Q with min dist[u]，这意味着您选择一个成本最低的选项。当你有更多的选择与相同的成本，你只需接受其中任何一个。

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