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).
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 ED -> 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
Your Task
| Node | Status | Shortest Distance from A | Previous Node |
| A | |||
| B | |||
| C | |||
| D | |||
| E | |||
| F | |||
| Z |
Shortest Path?
Length?
| Node | Status | Shortest Distance from A | Previous Node |
| A | |||
| B | |||
| C | |||
| D | |||
| E | |||
| F | |||
| Z |
Shortest Path?
Length?
Solution...
The solution for this challenge is available to full members!Find out how to become a member:
➤ Members' Area
LMC Simulator
Logic Gates Circuits
Network Designer
Flowchart Studio
Online Python IDE