Dijkstra’s Algorithm

Dijkstra’s Algorithm is an algorithm which is used to find the shortest path from one vertex (also known as the source vertex) to all the other vertices in a given graph. It is a type of greedy algorithm which always picks the next best solution and assuming that the end result will be the best solution. It generates the shortest path tree with a given source vertex as the root.

The algorithm is as follows-

1. We have to create a set which keeps the record of all the vertices that are included in the shortest paths. Initially this set would be empty.
2. The source vertex is assigned a distance of 0 while all other vertices are assigned distance values as infinite.
3. Till all vertices aren’t included in the set we created in step 1, we have to repeat the following steps — Select the vertex which is not yet included in the set but has the minimum distance. — Include that vertex in the set. — Update the distance of the vertex as explained below.

For updating the distance of a vertex X, all the adjacent vertices of X are iterated through. Then the distance of the adjacent vertex (let’s say Y) from X, that distance is added to the distance of X from the source vertex. The one which gives the least distance value is chose.

After doing these steps for all vertices we get the shortest distance from the source vertex. For the above algorithm, the time complexity comes down to O(V²). To reduce this time complexity even further, min heaps can be used.

If min heaps are used, the algorithm changes to the below explained one —

1. We have to create a min heap of size equal to the number of vertices. We have to assign each node of the min heap the vertex number and the distance of that vertex.
2. Same as above algorithm. Source vertex is assigned 0 while rest are assigned infinite value.
3. Till the main heap is emptied, the following steps are done — The vertex with minimum distance is taken out from min heap. — For every adjacent vertices update the distances (same as explained above).

Following this approach by using min heaps, it reduces the time complexity to O(ElogV). Hence there are two ways of Dijkstra’s algorithm but using min heaps reduces time complexity, hence this method is preferred.

The pseudo code for Dijkstra’s algorithm is as follows —

Dijkstra’s algorithm also has other ways of implementation. It can be used to calculate the shortest distance from source vertex to all the other vertices. But if required, it can also be used to calculate shortest distance from the source vertex to any other single target. In such a case, the algorithm changes slightly so that it stops after the picked minimum distance vertex is equal to the specified target.

One of the shortcomings of Dijkstra’s algorithm is that it fails for graphs containing negative weight edges. But then again, the algorithm can be modified a little so that it does give correct results for graphs with negative edges but that involves allowing a vertex to be visited multiple times. If that’s the case then the time complexity increases. One of the main advantages of this algorithm is it’s fast time complexity, it will be useless if it loses it’s fast time complexity. Hence, it is not used for graphs with negative weight edges.

Dijkstra’s algorithm has several applications and some of them are as follows-

• It is used in finding the shortest paths of graphs
• In social networking applications, it is used for suggesting “friends” or to derive important relations from the community graph of the social network.
• It is used in telephone networks.
• To find the locations on the map. The minimum distance from one location to another.
• It is used in designing of train, subway networks. Where the shortest path from one city to another needs to be routed.

These are some of the important points to remember about Dijkstra’s algorithm and how it works. The algorithm has also been explained here. So that’s the quick rundown of Dijkstra’s algorithm, hope you learned something new and had fun reading it.