我不确定确定性有一个通用的定义，但*** 将其定义为...

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

所以这需要输出的确定性和执行的确定性.无论你怎么看，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.