algorithm - Dijkstra 算法是确定性的吗？

Question

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

我说得对吗？如果我错了，您能否解释一下为什么它是确定性的，并举一个例子？

Answer 1

我不确定决定论是否有一个通用的定义，但维基百科defines it作为...

... 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.

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

Dijkstra 算法的执行在抽象意义上不是确定性的，因为final step是:

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.

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

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