In the following example, how does Dijkstra's algorithm find the shortest path?
I think we'll get abedz, while the shortest should be acedz.
3
-
5$\begingroup$ What have you tried? What are your steps? What textbooks are you using? The working of Dijkstra's algorithm is described in almost every algorithms textbook; to learn how it finds the shortest path in this graph, just execute the pseudocode by hand. If you think it gives the wrong answer, you almost certainly have a small mistake somewhere: double-check your work, and then write it down in the question. $\endgroup$– D.W. ♦Commented May 22, 2015 at 15:41
-
$\begingroup$ It seems like you are claiming Dijkstra's algorithm is wrong, so I second the suggestion of @D.W. $\endgroup$– JuhoCommented May 22, 2015 at 16:37
-
$\begingroup$ I specifically said "how does the algorithm find the shortest path", hence having no doubt that it CAN find it. $\endgroup$– qedCommented May 23, 2015 at 13:23
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You have a mistake in your steps, maybe because you misunderstood the algorithm.
The following table show the values i get when executing the algorithm:
a b c d e z
------------------------------------------
Distance 0 Inf Inf Inf Inf Inf
Visited F F F F F F
Predecessor - - - - - -
------------------------------------------
0 3 4 Inf Inf Inf
T F F F F F
- a a - - -
------------------------------------------
0 3 4 9 8 Inf
T T F F F F
- a a b b -
------------------------------------------
0 3 4 9 5 Inf
T T T F F F
- a a b c -
------------------------------------------
0 3 4 7 5 17
T T T F T F
- a a e c e
------------------------------------------
0 3 4 7 5 14
T T T T T F
- a a e c d
------------------------------------------
0 3 4 7 5 14
T T T T T T
- a a e c d
Then the shortest path is a -> c -> e -> d -> z with weight 14, as you correctly guessed.
Compare this table with your steps to find where is your mistake.
Important facts to take in count:
- Visited vertices are never re-visited.
- When a vertex has been marked as visited, the path to that vertex is the shortest route from the starting vertex.
