World's most popular travel blog for travel bloggers.

# [Solved]: Dijsktra's algorithm example

, ,
Problem Detail:

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.

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.