Path finding using Dijkstra’s Algorithm in under 2 minutes!
How to find shortest path between two points?
Well one possible solution is through Dijkstra’s Algorithm.
Look at the below Graph we want to find shortest path from S to D.
First we finalize the source And Destination.
We start at S and look at neighbours of S.
And store those neighbors in a priority queue according to their distance from S. We mark all the distances from Source Infinity at first, and if it is a neighbour of the current node we can update the distance.
Below you can see we maintain two tables, Other Nodes and Neighbouring nodes and we keep updating the distances in those tables.
For this Example, first A and B are visited and then we check neighbours of A and B.
If you check, closely, C can be visited via 2 paths, via A and via B, in that case we chose the path which gives us the shortest distance from S over all, there fore we can see that the distance of C is written down as “4” via B not “6” via A.
Finally when we reach the required end point, we retrace our steps back and get the shortest path!
And That was how you find shortest path between two points using Dijkstra’s Algorithm in under 2 minutes !