Dijkstra 算法 : What to do if there are two or more nodes with minimal weight?

Question

在 Dijkstra 算法中，如果算法中的某个点有两个或多个权重最小的节点，我该怎么办？

在维基百科中:http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm在步骤号6，它说

“将标记有最小暂定距离的未访问节点设置为下一个‘当前节点’，然后返回步骤 3。”

如果有两个或更多节点具有“最小暂定距离”怎么办。

谁能帮我算法？

Answer 1

简答

随便选一个。除非您有另一种启发式方法可以使用，否则您无法确定选择哪个更好。

更多解释

考虑将一些元素排序到数组中:

9 6 3 3 8

以最低优先排序是

3 3 6 8 9

如果您要查询该数组以确定最低值，则答案是 3 .其中 3没关系。

同样，如果您要获得更多信息。例如，假设这些整数实际上是浮点数并且是 按整数部分排序 .你可能会得到数组:

3.2  3.1  6.0  8.5  9.2

在这里，您可以使用另一种启发式方法，您也可以检查小数部分，然后可以确定 3.1是最低的。