Dijkstra's Shortest Path Algorithm

Dijkstra's Shortest Path Algorithm

• 
• In the following slides we want to find the shortest path from A to F considering that each edge is labelled with it's specific distance.
• We start with labelling the starting node A with 0, which stand for the total distance one has to travel from A to A. All other nodes are labelled with infinity.

Folie 2

• 
• In the first step we travel to all nodes which are reachable from A and are not yet visited. Then we update their distance to the minimum of their current distance and the distance travelled from A.
• Example: distance(E) = min{infinity, 14} = 14
• Since B, C, E had distance infinity beforehand, all of their distances will be updated.
• Now that we have visited node A, it gets marked as visited (yellow), so we don't visit it again.

Folie 3

• 
• We have already visited A, now we arbitrarily pick one of the nodes we have reached - in our case for example B. From B we can reach C and D (A is already visited).
• We see that the distance to C via B (10+7) is bigger than the current distance (9), so we do not update it's value.
• However the distance to D via B (7+15) is better than the current distance (infinity), so we update the value.
• As before, we now mark B as visited and continue with the algorithm.

Folie 4

• 
• Just as before, we pick an arbitrary node we have already reached and check, wheter we can reach the unvisited nodes in a more efficient way via the selected node.
• In our case we pick C and see, that the distance to E via C and the distance to D via C are reduced, so we update the values.
• As always, C is now marked as visited.

Folie 5

• 
• We pick node E and observe, that we can reach F in distance 20 via the path ACEF.
• We mark E as visited.

Folie 6

• 
• At last we pick node D and discover, that path ACDF is longer than the current distance, so we don't update the value.
• Since all paths have been visited by now, we conclude that the shortes path from A to F is ACEF.

Folie 7

• 
• These slides contain material that is licensed under the creative commons attribution-sharealike 4.0 international license.
• Therefore these slides are published under the same license.
• The material used in these slides are taken from the course "Einführung in die Informatik - Computational Thinking" and were created by Prof. O. Nierstrasz for classes at the University of Berne.
• Bildunterschrift: https://creativecommons.org/licenses/by-sa/4.0/