-1
$\begingroup$

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.

$\endgroup$
  • 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
3
$\begingroup$

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.
$\endgroup$

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