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.