Dijkstra的算法：如果有两个或多个权重最小的节点怎么办？ [英] Dijkstra's algorithm: What to do if there are two or more nodes with minimal weight?

问题描述

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

In Dijkstra's algorithm what should I do if there are two or more nodes with minimal weights at a point in the algorithm?

在Wikipedia中： http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm 。 6，它说

In wikipedia: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm at step no. 6, it says

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

"Set the unvisited node marked with the smallest tentative distance as the next 'current node' and go back to step 3."

如果有两个或多个节点的最小尝试距离怎么办？

What if there are two or more nodes with "smallest tentative distance".

有人可以帮助我解决该算法吗？

Can anyone help me with the algorithm?

推荐答案

简短答案

只需选择其中一个即可。除非您可以使用其他启发式方法，否则您将无法确定哪个更好。

Short Answer

Just pick either. Unless you have another heuristic to work with, you can't tell which would be better to pick.

考虑将某些元素排序到数组中：

Think about sorting some elements into an array:

9 6 3 3 8

排在最前面的是最低

3 3 6 8 9

如果要查询确定最低的那个数组，答案是 3 。哪一个 3 都没关系。

If you were to query that array to determine the lowest, the answer is 3. Which 3 doesn't matter.

类似地，如果您了解更多信息。举例来说，这些整数实际上是浮点数，并按整数部分排序。您可能会得到以下数组：

Similarly if you were to have some more information. Say for example that those ints were actually floats and were sorted by their integer parts. You might end up with the array:

3.2  3.1  6.0  8.5  9.2

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

Here you have another heuristic to work with, you can check the decimal part too, and you can determine that 3.1 is the lowest.

这篇关于Dijkstra的算法：如果有两个或多个权重最小的节点怎么办？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！