# Dijsktra's algorithm example [closed]

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.

• 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.
– D.W.
Commented May 22, 2015 at 15:41
• It seems like you are claiming Dijkstra's algorithm is wrong, so I second the suggestion of @D.W.
– Juho
Commented May 22, 2015 at 16:37
• I specifically said "how does the algorithm find the shortest path", hence having no doubt that it CAN find it.
– qed
Commented May 23, 2015 at 13:23

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:

1. Visited vertices are never re-visited.
2. When a vertex has been marked as visited, the path to that vertex is the shortest route from the starting vertex.