Dijkstra 算法是确定性的吗? [英] Is Dijkstra's algorithm deterministic?

问题描述

我认为 Dijkstra 的算法是确定的，因此如果您选择相同的起始顶点，您将获得相同的结果(到每个其他顶点的距离相同).但我不认为它是确定性的(它为每个操作定义了以下操作)，因为这意味着它首先不必搜索最短距离.

我说得对吗?如果我错了，请您解释一下为什么它是确定性的，并举例说明?

解决方案

我不确定确定性有一个通用的定义，但维基百科 将其定义为...

<块引用>

...一种算法，给定特定输入，将始终产生相同的输出，而底层机器始终通过相同的状态序列.

所以这需要输出的确定性和执行的确定性.无论你怎么看，Dijkstra 算法的输出都是确定性的，因为它是最短路径的长度，而这样的长度只有一个.

抽象意义上的 Dijkstra 算法的执行不是确定性的，因为 最后一步是:

<块引用>

6. 否则，选择标记为最小暂定距离的未访问节点，将其设置为新的当前节点"，并返回步骤 3.

如果有多个节点的最小暂定距离相同，算法可以任意选择一个.这不会影响输出，但会影响算法中的操作顺序.

Dijkstra 算法的一个特定实现，然而，可能是确定性的，因为节点将存储在一个确定性的数据结构中，如最小堆.这将导致每次运行程序时都选择相同的节点.尽管哈希表盐之类的东西即使在这里也可能会影响确定性.

I think that Dijkstra's algorithm is determined, so that if you choose the same starting vertex, you will get the same result (the same distances to every other vertex). But I don't think that it is deterministic (that it has defined the following operation for each operation), because that would mean that it wouldn't have to search for the shortest distances in the first place.

Am I correct? If I'm wrong, could you please explain why it is deterministic, and maybe give an example?

解决方案

I'm not sure there is a universal definition of determinism, but Wikipedia defines it as...

... an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states.

So this requires both determinism of the output and determinism of the execution. The output of Dijkstra's algorithm is deterministic no matter how you look at it, because it's the length of the shortest path, and there is only one such length.

The execution of Dijkstra's algorithm in the abstract sense is not deterministic, because the final step is:

6. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3.

If there are multiple nodes with the same smallest tentative distance, the algorithm is free to select one arbitrarily. This doesn't affect the output, but it does affect the order of operations within the algorithm.

A particular implementation of Dijkstra's algorithm, however, probably is deterministic, because the nodes will be stored in a deterministic data structure like a min heap. This will result in the same node being selected each time the program is run. Although things like hashtable salts may also affect determinism even here.

这篇关于Dijkstra 算法是确定性的吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！