# WP pseudocode for Dijkstra does not work

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):

# 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?

• 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. – Paresh Apr 5 '13 at 13:22

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$