-1
$\begingroup$

I mean Dijkstra's algorithm for the shortest path.

In all descriptions that I saw (including wikipedia), on every step, it always selects the nearest neighbor based on examining their weights.

Imagine that we have following paths from source A to destination B (I will list weights of different paths, not full graph - for brevity):

1: $$A {19\atop\longrightarrow} A_1 {2\atop \longrightarrow} A_2{2\atop \longrightarrow} A_3{10\atop \longrightarrow} B$$

2: $$A {5\atop\longrightarrow} A_4 {10\atop \longrightarrow} A_5{10\atop \longrightarrow} A_6{5\atop \longrightarrow} B$$

3: $$A {2\atop\longrightarrow} A_7 {15\atop \longrightarrow} A_8{15\atop \longrightarrow} A_9{10\atop \longrightarrow} A_{10} {10\atop \longrightarrow} B$$

If Dijkstra always select the neighbor with smallest weight, it will always go for #3 - although it is the heaviest path!

Where am I wrong? Does anybody has a 'working' pseudo-code for Dijkstra algorithm?

$\endgroup$
  • 4
    $\begingroup$ Wikipedia has a 'working' pseudo-code for Dijkstra's algorithm. Instead of assuming that evaluating the smallest distance first is the same as taking that path, you should try to apply the pseudo-code completely and correctly on your example by hand. Work it out till the end, and if you still have doubts, ask again. $\endgroup$ – Paresh Apr 5 '13 at 13:22
2
$\begingroup$

What's wrong with the Wikipedia pseudo code?

The Dijkstra algorithm according to their pseudo code just looks at $A_7$ first , then $A_4, A_5 \dots$

The rule of choice expresses a priority. If necessary every vertex of $G$ is considered. It takes some time until $A_1$ is considered, but it eventually happens:

  1. $A$ is considered (Line 12)
  2. New distances for $A_1,A_4,A_7$ are $19,5,2$ (Lines 20 and 24)
  3. $A_7$ is now minimal and the next vertex (Line 12)
  4. The new distance for $A_8$ is $17$ (Line 20 and 24)
  5. $A_4$ is now minimal (Line 12)
  6. The new distance for $A_5$ is $15$ (Line 20 and 24)
  7. $A_5$ is now minimal (Line 12)
  8. The new distance for $A_6$ is $25$ (Line 20 and 24)
  9. $A_8$ is now minimal (Line 12)
  10. The new distance for $A_9$ is $32$ (Line 20 and 24)
  11. $A_1$ is now minimal (Line 12)
  12. $\dots$
$\endgroup$

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.