Dijkstra's Algorithm

This algorithm is used to get the shortest path from the source node to all other nodes.

Data structures Required: Min Heap(Priority Queue, Set, etc), Arrays.

Algorithm:

• Initialize the distance array with infinity so that later we can update them with minimum distance from the source. And initialize the distance of the source from the source itself with 0.

• Push the pair {0, source} into the min heap.

• For every element at the top of the min heap take it out and look for its adjacent nodes. If the current reachable distance is better than the previous distance mentioned in the distance array update the distance array with the new distance and push this node and its updated distance into the queue.

• A node with a lower distance will always be at the top of the min heap. These steps will be repeated until the min heap is not empty.

• At the end we will get a resultant distance array with min distances of the nodes from the source.

CODE:

Dijkstra's Algorithm implementation using Priorioty Queue: