Dijkstra’s Shortest Path Algorithm

Posted on January 31, 2018 by Administrator Posted in A Level Concepts, A Level Quiz, Algorithms, Computer Science, Computing Concepts, Solved Challenges

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).

GraphStep 123456789

Start by setting the starting node (A) as the current node.

Check all the nodes connected to A and update their “Distance from A” and set their “previous node” to “A”.

Set the current node (A) to “visited” and use the closest unvisited node to A as the current node (e.g. in this case: Node C).

Check all unvisited nodes connected to the current node and add the distance from A to C to all distances from the connected nodes. Replace their values only if the new distance is lower than the previous one.

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

Set the current node C status to Visited.
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.

B -> D 3+5 = 8 < 10 – Change Node D

Next “Current Node” will be D as it has the shortest distance from A amongst all unvisited nodes.

D -> E 8+2 = 10 < 12 – Change Node E
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

E -> Z 10+5 = 15 > 14 – We do not change node Z.

We found the shortest path from A to Z.
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