1
$\begingroup$

Considering the following nodes with edge weights in red, Dijkstra's shortest path algorithm seems to return incorrect results, at least by the definition of the steps on wikipedia. By those rules, the distance from 0 to 2 will be calculated by passing through 1 instead of 3.

The final distances (from 0) would come out to:

0 -> 0

1 -> 0.2

2 -> 1000.2

3 -> 0.5

The weights in this case are bi-directional but I don't see a way for information of the connection between 2 and 3 to ever affect the final distance between 0 and 2. Am I missing something about the limitations of this algorithm on this type of graph or are the steps listed incorrect?

example cycle

$\endgroup$
2
  • $\begingroup$ In which order do you evaluate the nodes? What exactly do you do/get evaluating node 3? $\endgroup$
    – greybeard
    Jan 1 '20 at 10:49
  • $\begingroup$ @greybeard I misunderstood which way to propagate the current node from the instructions. I was originally taking the neighbor that had the lowest tentative distance and following a path from 0 -> 1 -> 2 -> 3. Node 3 would have a distance of 0.5 since it was one of the first values I calculated and is much lower than 1000.3. $\endgroup$
    – tirefire
    Jan 1 '20 at 21:39
0
$\begingroup$

In the wikipedia article you linked, the final distance is only computed when the node is visited (step 6). The tentative distance is (re)calculated each time to visit a parent of a node, and overwritten if it's smaller (step 3).

So in your example,

  1. We visit node 0. We set tentative(1) = 0.2, tentative(3) = 0.5
  2. We visit node 1, since it has the smallest tentative distance. We set tentative(2) = 1000.2
  3. We visit node 3. Since 0.6 < 1000.2, we set tentative(2) = 0.6
  4. We visit node 2. Its final distance is tentative(2), which is currently 0.6
$\endgroup$
1
  • $\begingroup$ Oh, I clearly misunderstood step 6. It means the lowest global distance, not the distance relative to the current node! This was extremely helpful. Thanks! $\endgroup$
    – tirefire
    Jan 1 '20 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.