理解 Dijkstra 算法
Understanding Dijkstra Algorithm
我正在尝试了解用于查找最短路径的 Dijkstra 算法。
我想出了这个例子，其中顶部 table 对应于左下角的图像。
现在，我的问题是我不明白从第 1 步到第 2 步的过渡：
当我们处于 UX 时，我们可以通过将 X 到 V 的成本（即 2）添加到我们当前的成本（即 1；UX 的成本）来前往 UXV。所以总和为 3，但由于这个我比我们已经发现的 2 大，所以我们不更改它。在第 1 步中，我们有两个具有相同成本的选项； UXY和UXV，但是为什么算法选择去UXY而不是UXV？
提前致谢！
当您有两个或多个成本相同的选项时，您选择哪个选项没有任何区别。
在 Dijkstra's algorithm Wikipedia article 中有一段包含用于实现算法的伪代码。可以看到伪代码中有一行u ← vertex in Q with min dist[u]，意思是你选择一个成本最低的选项。当您有更多选择且成本相同时，您只需选择其中的任何一个。
对于您的具体示例，这意味着您也可以转到 UXV 而不是 UXY。 可能会导致更多的步骤，但算法完成后的最终结果是一样的。
我正在尝试了解用于查找最短路径的 Dijkstra 算法。
我想出了这个例子，其中顶部 table 对应于左下角的图像。
现在，我的问题是我不明白从第 1 步到第 2 步的过渡：
当我们处于 UX 时，我们可以通过将 X 到 V 的成本（即 2）添加到我们当前的成本（即 1；UX 的成本）来前往 UXV。所以总和为 3，但由于这个我比我们已经发现的 2 大，所以我们不更改它。在第 1 步中，我们有两个具有相同成本的选项； UXY和UXV，但是为什么算法选择去UXY而不是UXV？
提前致谢！
当您有两个或多个成本相同的选项时，您选择哪个选项没有任何区别。
在 Dijkstra's algorithm Wikipedia article 中有一段包含用于实现算法的伪代码。可以看到伪代码中有一行u ← vertex in Q with min dist[u]，意思是你选择一个成本最低的选项。当您有更多选择且成本相同时，您只需选择其中的任何一个。
对于您的具体示例，这意味着您也可以转到 UXV 而不是 UXY。 可能会导致更多的步骤，但算法完成后的最终结果是一样的。