Dijkstra’s Shortest Path Algorithm

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
Dijkstra-Algorithm
Dijkstra-Algorithm-Step-1Start by setting the starting node (A) as the current node.
Dijkstra-Algorithm-Step-2Check all the nodes connected to A and update their “Distance from A” and set their “previous node” to “A”.
Dijkstra-Algorithm-Step-3Set 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).
Dijkstra-Algorithm-Step-4Check 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

Dijkstra-Algorithm-Step-5Set 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.
Dijkstra-Algorithm-Step-6B -> 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.

Dijkstra-Algorithm-Step-7D -> 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

Dijkstra-Algorithm-Step-8E -> Z 10+5 = 15 > 14 – We do not change node Z.
Dijkstra-Algorithm-Step-9We 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


Apply the steps of the Dijkstra’s Algorithm to find the shortest path from A to Z using the following graph:
Dijkstra-Algorithm-Graph

Node Status Shortest Distance from A Previous Node
A
B
C
D
E
F
Z

Shortest Path?

Length?

Share Button
Tagged with: ,