Is Dijkstra's algorithm deterministic?

Question

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?

Dystrophy

Answer 1

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.

Pickaninny

"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." Usually, the output is the path itself - i.e. a sequence of nodes - which may not be unique. – Spunky

Very true. Although there are also variants that produce all shortest paths, and those would again be deterministic. – Pickaninny

Oh, I didn't mean that implementations which return a path (but only one path) aren't deterministic; it depends on things like which order you iterate over a node's neighbours in, and which order nodes of equal priority are polled from the priority queue, which are implementation details (e.g. if nodes are stored in a hashtable, or the priority queue is a heap) but is generally deterministic. It would only be non-deterministic if you used a randomized data structure. So I agree with the rest of your answer. – Spunky

In case it helps anyone in the future, I just posted an answer here that visualizes the inner workings of BGL's dijkstra, and comes up with ways to ensure proper tie-breakers if you really need to. – Cryptology

Answer 2

Allow me to expand on Thomas's answer.

If you look at an implementation of Dijkstra, such as this example: http://graphonline.ru/en/?graph=NnnNwZKjpjeyFnwx you'll see a graph like this

In the example graph, 0→1→5, 0→2→5, 0→3→5 and 0→4→5 are all the same length. To find "the shortest path" is not necessarily unique, as is evidenced by this diagram.

Using the wording on Wikipedia, at some point the algorithm instructs us to:

select the unvisited node that is marked with the smallest tentative distance.

The problem here is the word the, suggesting that it is somehow unique. It may not be. For an implementation to actually pick one node from many equal candidates requires further specification of the algorithm regarding how to select it. But any such selected candidate having the required property will determine a path of the shortest length. So the algorithm doesn't commit. The modern approach to wording this algorithm would be to say:

select any unvisited node that is marked with the smallest tentative distance.

From a mathematical graph theory algorithm standpoint, that algorithm would technically proceed with all such candidates simultaneously in a sort of multiverse. All answers it may arrive at are equally valid. And when proving the algorithm works, we would prove it for all such candidates in all the multiverses and show that all choices arrive at a path of the same distance, and that the distance is the shortest distance possible.

Then, if you want to use the algorithm to just compute one such answer because you want to either A) find one such path, or B) determine the distance of such a path, then it is left up to you to select one specific branch of the multiverse to explore. All such selections made according to the algorithm as defined will yield a path whose length is the shortest length possible. You can define any additional non-conflicting criteria you wish to make such a selection.

The reason the implementation I linked is deterministic and always gives the same answer (for the same start and end nodes, obviously) is because the nodes themselves are ordered in the computer. This additional information about the ordering of the nodes is not considered for graph theory. The nodes are often labelled, but not necessarily ordered. In the implementation, the computer relies on the fact that the nodes appear in an ordered array of nodes in memory and the implementation uses this ordering to resolve ties. Possibly by selecting the node with the lowest index in the array, a.k.a. the "first" candidate.

If an implementation resolved ties by randomly (not pesudo-randomly!) selecting a winner from equal candidates, then it wouldn't be deterministic either.

Dijkstra's algorithm as described on Wikipedia just defines an algorithm to find the shortest paths (note the plural paths) between nodes. Any such path that it finds (if it exists) it is guaranteed to be of the shortest distance possible. You're still left with the task of deciding between equivalent candidates though at step 6 in the algorithm.

Mindy

In case it helps anyone in the future, I just posted an answer here that visualizes the inner workings of BGL's dijkstra, and comes up with ways to ensure proper tie-breakers if you really need to. – Cryptology

Answer 3

As the tag says, the usual term is "deterministic". And the algorithm is indeed deterministic. For any given input, the steps executed are always identical.

Compare it to a simpler algorithm like adding two multi-digit numbers. The result is always the same for two given inputs, the steps are also the same, but you still need to add the numbers to get the outcome.

Wainscot

Answer 4

By deterministic I take it you mean it will give the same answer to the same query for the same data every time and give only one answer, then it is deterministic. If it were not deterministic think of the problems it would cause by those who use it. I write in Prolog all day so I know non-deterministic answers when I see them.

---

Here I just introduced a simple mistake in Prolog and the answer was not deterministic, and with a simple fix it is deterministic.

Non-deterministic

spacing_rec(0,[]).
spacing_rec(Length0,['  '|T]) :-
    succ(Length,Length0),
    spacing_rec(Length,T).

?- spacing(0,Atom).
Atom = '' ;
false.

Deterministic

spacing_rec(0,[]) :- !.
spacing_rec(Length0,['  '|T]) :-
    succ(Length,Length0),
    spacing_rec(Length,T).

?- spacing(0,Atom).
Atom = ''.

Depside

No, that's not a sufficient condition. A deterministic algorithm also has to always follow the same states to get to the outcome. That's not a given on multicore CPU's anymore, even for a simple algorithm as adding a million integers. The final outcome will be the same, but the intermediate sums may differ depending on your number of CPU cores. – Wainscot

@Wainscot I think "intermediate states" should be interpreted as meaning the intermediate states in some formal model of computation defined by the programming language's semantics, not the intermediate states of a physical computer. If this term were defined in terms of a physical computer, it would be impossible to determine by theory instead of experiment whether an algorithm is deterministic. Even defining "instantaneous state" for a physical computer is hard, because whether or not two physical components are in particular states at the same time is technically relative to the observer. – Spunky

Answer 5

I will try and keep this short and simple, there are so many great explanations on this on here and online as well, if some good research is done of course.

Dijkstra's algorithm is a greedy algorithm, the main goal of a Dijsktra's algorithm is to find the shortest path between two nodes of a weighted graph.

Wikipedia does a great job with explaining what a deterministic and non-deterministic algorithms are and how you can 'determine' which algorithm would fall either either category:

From Wikipedia Source:

Deterministic Algorithm:

In computer science, a deterministic algorithm is 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. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently.

Formally, a deterministic algorithm computes a mathematical function; a function has a unique value for any input in its domain, and the algorithm is a process that produces this particular value as output.

Nondeterministic Algorithm

In computer science, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition.

So going back to the goal of Dijkstra's algorithm is like saying I want to get from X location to Z location but to do that I have options going through shorter nodes that will get my to my end a lot quicker and more efficiently than other longer routes or nodes...

Thinking through cases where Dijsktra's algorithm could be deterministic would be a good idea as well.

Summation