Dijkstra’s algorithm to find the shortest path.
Question:
Using Dijkstra’s algorithm to find the shortest path from home node 1 to all other nodes as per Fig 9.2. The travel time given for links 1-4, 5-6 & 9-10 are 8, 9 & 8 respectively.
Figure 9.2:
Summary:
In this question, they have given a 12-node graph connected with undirected edges. The start node is node-1. Using Dijkstra’s algorithm, the shortest distance is found from node-1 to all other 11 nodes in the graph.
Explanation:
Dijkstra’s algorithm:
It is an algorithm used to find the shortest path from one vertex/node to all other vertices. It can be applied for any weighted, non-weighted, directed, and undirected graphs.
Using Dijkstra’s algorithm to find the shortest path:
Starting node :1
Distance array from node-1 to all other nodes,
D[ ]=
0 | 13 | – | 8 | 5 | – | – | – | – | – | – | – |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
Step 1:
From node-1, shortest to node-1 is 5 In the shortest node is 5. so expand 5.
Step 2:
Here the shortest node is 4 so expand 4.
Step 3:
The shortest node is 2 but there is nothing to expand so expand 6.
Step 4:
Here, there is nothing to expand in node 3, so expand 7.
Step 5:
Next, expand node 8.
Step 6:
The shortest node is 9 but there is nothing to expand so expand 10.
Step 7:
There is nothing to expand in node-11 and node 12.
Final diagram for Dijkstra’s algorithm to find the shortest path is:
The shortest path from node 1 to all other nodes are:
NODE | PATH | DISTANCE |
2 | 1-2 | 13 |
3 | 1-5-6-3 | 22 |
4 | 1-4 | 8 |
5 | 1-5 | 5 |
6 | 1-5-6 | 14 |
7 | 1-4-7 | 23 |
8 | 1-4-7-8 | 27 |
9 | 1-5-6-9 | 33 |
10 | 1-5-6-10 | 39 |
11 | 1-5-6-10-11 | 49 |
12 | 1-4-7-8-12 | 40 |
Also, read Create an SQL table and schema and explain any constraints.