I mean Dijkstra's algorithm for the shortest path.
Sorry for noob question.
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):
- $19 \to 2 \to 2 \to 10$
- $5 \to 10 \to 10 \to 10 \to 5$
- $2 \to 15 \to 15 \to 10 \to 2$
If Dijkstra always select the neighbor with smallest weight,
it will always go for 3. – although it leads to the heaviest path!
Where am I wrong?
Does anybody have a 'working' pseudo-code for Dijkstra algorithm?
Thanks.
Best Answer
The point of Dijkstra's is that it is not greedy like some others, sure it will look at the node after the first edge of 3 first. But then it will look at 2, and then the next vertex on 2, updating shortest paths as it goes. Eventually the 19 to start 1 off will be the next best choice, and then from there it will find the nice 2's and it will catch up along 1 so to speak.
It would help to see the graph to give you a better idea what's going on. Working pseudocode is on the Wikipedia page.