Do you know, Google maps use Dijkstra Algorithm to show shortest distance between source and destination. Also Airlines use Dijkstra to plan flight paths that minimize fuel consumption and reduce travel time.

Dijkstra determines the shortest path and distance from source to all destinations in the graph. To keep the track, we need 2 sets of nodes viz., Settled and Unsettled.

Settled nodes are those with a known minimum distance from the source. Whereas Unsettled nodes set gathers nodes that we can reach from the source but we don’t know the minimum distance from starting node.

Finding Shortest Paths: The Simple Steps

1. Set distance to startNode to Zero
2. Set all other distances to an infinite value
3. we add startNode to unsettled nodes set
4. while unsettled nodes set is not empty , follow below steps :
   • Choose an evaluation node from unsettled nodes set, it should be one with minimum distance from the source
   • Calculate new distances to direct neighbors by keeping the lowest distance at each evaluation
   • Add neighbors that are not yet settled to unsettled node set

Go through below figure and the evaluation table:

Leetcode Problems which depend on Dijkstra are as below:

1. https://leetcode.com/problems/path-with-maximum-probability/
2. https://leetcode.com/problems/network-delay-time/
3. https://leetcode.com/problems/the-maze-ii/
4. https://leetcode.com/problems/the-maze-iii/
5. https://leetcode.com/problems/path-with-minimum-effort/
6. https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/