Edsger W.Dijkstra invented Dijkstra’s algorithm to find the shortest path for the required node between multiple nodes in the graph to design a shortest-path tree.
What Is Dijkstra’s Algorithm?
Dijkstra’s algorithm is used to find the shortest path between the two mentioned vertices of a graph by applying the Greedy Algorithm as the basis of principle.
For Example: Used to find the shortest between the destination to visit from your current location on a Google map.
Now let’s look into the working principle of Dijkstra’s algorithm.
Principle of Dijkstra’s Algorithm
To find the shortest path between two given vertices of a graph, we will follow the following mentioned steps of the algorithm/approach, which are:
if dist(u) + len(u,v) < dist(v)
dist(v) = dist(u) + len(u,v)
Where,
dist(u) = Source Node
dist(v) = Destination Node
Note: By default, the source node's immediate and non-immediate distance to the other nodes in the graph is “∞ (Infinite).”
For Example: Find the shortest path for the given graph.
1. We will find the shortest path from node A to the other nodes in the graph, assuming that node A is the source.
2. For node B, apply the above-discussed algorithm, then on applying values:
if 0 + 20 < ∞
>[TRUE]
Node A to Node B = 20
3. For node C, on applying the approach from node A, we have:
if 0 + 50 < ∞
>[TRUE]
Node A to Node B = 50
4. For node C, from node B, on applying the algorithm, we have:
if 20 + 10 < ∞
>[TRUE]
Node B to Node C = 30
5. By the value obtained from step 3, we change the shortest distance between node A to Node C to 30 from the previous distance of 50.
Now that we are clear with the approach behind the algorithm let’s apply it for implementation.
Implementing Dijkstra’s Algorithm
Let’s apply Dijkstra’s Algorithm for the graph given below, and find the shortest path from node A to node C:
Solution:
1. All the distances from node A to the rest of the nodes is ∞.
2. Calculating the distance between node A and the immediate nodes (node B & node D):
For node B,
Node A to Node B = 3
For node D,
Node A to Node D = 8
3. Choose the node with the shortest distance to be the current node from unvisited nodes, i.e., node B. Calculating the distance between node B and the immediate nodes:
For node E,
Node B to Node D = 3+5 = 8
For node E,
Node B to Node E = 3+6 = 9
4. Choose the node with the shortest distance to be the current node from unvisited nodes, i.e., node D. Calculating the distance between node D and the immediate nodes:
For node E,
Node D to Node E = 8+3 = 11 ( [9 < 11] > TRUE: So, No Change)
For node F,
Node D to Node F = 8+2 = 10
5. Choose the node with the shortest distance to be the current node from unvisited nodes, i.e., node E. Calculating the distance between node E and the immediate nodes:
For node C,
Node E to Node C = 9+9 = 18
For node F,
Node E to Node F = 9+1 = 10
6. Choose the node with the shortest distance to be the current node from unvisited nodes, i.e., node F. Calculating the distance between node F and the immediate nodes:
For node C,
Node F to Node C = 10+3 = 13 ([18 < 13] FALSE: So, Change the previous value)
So, after performing all the steps, we have the shortest path from node A to node C, i.e., a value of 13 units.
Conclusion
In this article on ‘what is Dijkstra’s Algorithm,’ we looked into the information related to the approach and its working principle. We also consolidated our understanding of the algorithm by solving an example.
You can refer to Simplilearn’s Cyber Security Expert course to further understand the working of the algorithm and its application. After completing this professional course, you’ll become more proficient with terms related to data structures and algorithms and their related terms.
If you have any questions about this article on ‘what is Dijkstra’s Algorithm’. Feel free to mention them in the comment section at the bottom of this page. Our expert team will help you solve your queries at the earliest.
