Dijkstra’s single source shortest path algorithm

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.

Reference: Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne

2 thoughts on “Dijkstra’s single source shortest path algorithm

  1. Pingback: Indexed Min-Priority Queue C++ implementation | Everything Under The Sun

  2. Pingback: A* search algorithm | Everything Under The Sun

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s