In the following example, how does Dijkstra's algorithm find the shortest path?

enter image description here

I think we'll get abedz, while the shortest should be acedz.

  • 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. May 22 '15 at 15:41
  • $\begingroup$ It seems like you are claiming Dijkstra's algorithm is wrong, so I second the suggestion of @D.W. $\endgroup$ – Juho May 22 '15 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$ – qed May 23 '15 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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.