Cheap and Secure Web Hosting Provider : See Now

[Solved]: Dijsktra's algorithm example

, , No Comments
Problem Detail: 

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.

Asked By : qed

Answered By : JosEduSol

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.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42874

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback