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:

Dijkstra's algorithm to find the shortest path.

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 step 1 of Dijkstra's algorithmIn the shortest node is 5. so expand 5.

 

Step 2:

Here the shortest node is 4 so expand 4.

step 2 of Dijkstra's algorithm

Step 3:

The shortest node is 2 but there is nothing to expand so expand 6.

step 3 of Dijkstra's algorithm

Step 4:

Here, there is nothing to expand in node 3, so expand 7.

step 4 of Dijkstra's algorithm

 

Step 5:

 Next, expand node 8.

step 5 of Dijkstra's algorithm

Step 6:

The shortest node is 9 but there is nothing to expand so expand 10.

step 6 of Dijkstra's algorithm

 

Step 7:

There is nothing to expand in node-11 and node 12.

step 7 of Dijkstra's algorithm

 

Final diagram for Dijkstra’s algorithm to find the shortest path is:

Dijkstra's algorithm to find the shortest path of given diagram

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.

 

Share this post

Leave a Reply

Your email address will not be published. Required fields are marked *