Dijkstra’s algorithm solves the single source shortest path problem for weighted directed graphs having non-negative edge costs. Given a weighted directed graph and a source vertex s, it finds shortest paths from s to every other vertex v.
It is a greedy algorithm very similar to the Prim’s MST algorithm, the only difference being that in each iteration, Prim’s algorithm always chooses the closest vertex to the tree while Dijkstra’s algorithm always chooses the closest vertex to the source. It constructs a shortest path tree rooted at the source.
The algorithm works as follows:
- Consider vertices in increasing order of distance from source
- Add vertex to shortest path tree and relax all edges pointing from that vertex (relaxation means decreasing the distance from the source to a vertex if a shorter path is available from the source to that vertex via the newly added vertex to the tree)
The pseudo code for the algorithm is as follows:
An efficient implementation of Dijkstra’s algorithm requires the use of an indexed min-priority queue because the relaxation procedure requires the ability to decrease the keys already in the priority queue.
Running time analysis: Each edge is relaxed at most once and each edge relaxation might take O(log V) time to decrease a key in the priority queue, so the overall running time of Dijkstra’s algorithm with indexed priority queue is O(E log V).
Take a look at the C++ implementation.
Try your hand at problem SHPATH, which uses this idea.