Example
Let’s consider a road network represented as a graph where cities are the nodes and
roads between cities are the edges. We’ll use Dijkstra’s algorithm to find the shortest
path from a source city to a destination city.
The following graph displays the houses P, Q, R, S, T, U, V, and W as vertices, and
the roads connecting them as edges. The time, expressed in hours, that the car
takes to drive between each house is indicated by the numbers on the sides.
.
Step 1 – Start at the source node (let’s say A) with distance 0 and all other nodes
to infinity.
.
Step 2 – We mark the node A as visited.
A —> B, Cost of AB is 3, (Shortest Distance)
A —> E, Cost of AE is 4
A —> H, Cost of AH is 5
We have to find the minimum cost. So, we update the shortest distance (AB, 3).
.
Step 3 – We mark the node B as visited.
A —> B —> C, Cost of ABC is 8
A —> B —> E, Cost of ABE is 5
A —> E, Cost of AE is 4, (Shortest Distance)
A —> H, Cost of AH is 5
We have to find the minimum cost. So, we update the shortest distance (AE, 4).
.
Step 4 – We mark the node E as visited.
A —> B —> C, Cost of AC is 8
A —> E —> F, Cost of AEF is 6
A —> E —> G, Cost of AEG is 7
A —> H, Cost of AH is 5, (Shortest Distance)
We have to find the minimum cost. So, we update the shortest distance (AH, 5).
.
Step 5 – We mark the node H as visited.
A —> B —> C, Cost of AC is 8
A —> E —> F, Cost of AEF is 6, (Shortest Distance)
A —> E —> G, Cost of AEG is 7
A —> H —> G, Cost of AHG is 7
We have to find the minimum cost. So, we update the shortest distance (AEF, 6).
.
Step 6 – We mark the node F as visited.
A —> B —> C, Cost of AC is 8
A —> E —> F —> D, Cost of AEFD is 7, (Shortest Distance)
A —> E —> G, Cost of AEG is 7
A —> H —> G, Cost of AHG is 7
We have to find the minimum cost. So, we update the shortest distance (AEFD, 7).
.
Step 7 – We mark the node D as visited.
A —> B —> C, Cost of AC is 8
A —> E —> G, Cost of AEG is 7, (Shortest Distance)
A —> H —> G, Cost of AHG is 7
We have to find the minimum cost. So, we update the shortest distance (AEG, 7).
.
Step 8 – We mark the node G as visited.
A —> B —> C, Cost of AC is 8, (Shortest Distance)
We have to find the minimum cost. So, we update the shortest distance (ABC, 8).
Also, mark the node C as visited.
Dijkstra’s Algorithm is complete.
.
Note – I have just solved an array which has the shortest distance from source node A
to the remaining vertices. This is the single source shortest path which we have come
across now.
