Dijkstra’s Shortest Path Algorithm is an algorithm used to find the shortest path between two nodes of a weighted graph.
Before investigating this algorithm make sure you are familiar with the terminology used when describing Graphs in Computer Science.
Let’s decompose the Dijkstra’s Shortest Path Algorithm step by step using the following example: (Use the tabs below to progress step by step).
C -> B: 2 + 1 = 3 < 4 – Change Node B
C -> D: 2 + 8 = 10 < ∞ – Change Node D
C -> E: 2 + 10 = 12 < ∞ – Change Node E
We then repeat the same process always picking the closest unvisited node to A as the current node.
In this case node B becomes the current node.
Next “Current Node” will be D as it has the shortest distance from A amongst all unvisited nodes.
D -> Z 8+6 = 14 < ∞ – Change Node Z
We found a path from A to Z but it may not be the shortest one yet. So we need to carry on the process.
Next “Current Node”: E
Read the path from Z to A using the previous node column:
Z > D > B > C > A
So the Shortest Path is:
A – C – B – D – Z with a length of 14
Apply the steps of the Dijkstra’s Algorithm to find the shortest path from A to Z using the following graph:
|Node||Status||Shortest Distance from A||Previous Node|