Dijkstra’s Algorithm: A Critical Review

Dijkstra’s algorithm is a method that can find the shortest path from one single vertex, i.e., the source to all other vertices of the graph, given that every edge has some positive weight. The shortest path problem is one that we very often face in real life situations. Even google maps, which is now a staple for everyone, applies Dijkstra’s algorithm to figure out the best way to reach from point A to B.

Introduction

Edsger Dijkstra came up with Dijkstra's algorithm in 1956, while trying to find the shortest route from Rotterdam to Groningen- which he then published 3 years later.

Dijkstra’s algorithm is an example of a greedy algorithm. Greedy algorithms build solutions by choosing the option that looks best at each step. The hope is that everything will work out at the end, but it’s not always guaranteed! However, Dijkstra also applies the principle of dynamic programming because it uses the previously calculated distances to update total path distance, thereby reusing calculations of sub problems, which is the core principle of dynamic programming.

How it works

Dijkstra’s algorithm works by maintaining two sets of vertices. The first set contains the vertices that are already included in the shortest-path tree, and the second set contains the vertices that are not yet included. At each iteration, we find the vertex that is in the second set (the unvisited vertices) and has a minimum distance from the source. In this way, we ensure that we select only those vertices which are reachable and not yet included in our path.

The algorithm continues until all vertices have been visited, i.e., either added to or removed from this set of visited nodes. If there are no more unvisited nodes left, then stop; otherwise continue with another iteration until all nodes have been added to this set of visited nodes.

Dijkstra can be applied to both directed as well as undirected graphs.

Pseudo Code

Dijkstra works backwards by setting all distances of graph vertices from source as infinity and then visiting every node to find minimum distance of every sub path.

Minimum distance in every iteration is extracted using a priority queue. Dijkstra utilizes 2 arrays- distance[] to keep track of minimum distance from source as well as previous[] to keep track of the actual vertices in the shortest path.

In case we want to find the path from source to a specific target, instead of them all, Dijkstra can be modified a little to end the program when that specific target is reached.

A Practical Demonstration

Actual Implementation

Output of above Code

Thus we observe that result from both code as well as output when problem is solved by hand comes out to be the same.

Time Complexity

Dijkstra algorithm is majorly implemented in 3 ways, each having different time complexities. The method of implementation used depends not only on the method that takes the least time but also depends on the type of problem that is to be solved.

One such method is Priority queue using List data structure- this gives the highest time complexity of O(V²).

Time Complexity of the most common implementation of Dijkstra comes out as: O((V+ E) Log V) which is equivalent to O(E Log V),where, E is the number of edges and V is the number of vertices. This low complexity is possible due to implementation of priority queue using Binary heap as data structure. This can be calculated by considering the pseudo code: Extracting min from priority queue takes Log V, while the inner loop passing through unvisited edges for every minimum vertex where actual cost calculation occurs takes time (E+V). Thus our final complexity becomes (V+E) Log V i.e. O(E Log V).

This time complexity can be reduced even further by implementation of priority queue with Fibonacci heap, which takes constant time in decrease key operation (for finding min) instead of heap’s O(Log n). Hence the final complexity comes as O(E + V Log V).

Applications

Dijkstra, as we’ve already established is very frequently applied in real life situations, here are a few examples:

1. Utilized in Google Maps for finding best route.
2. Used in social networking applications to give a list of people that a user might know.
3. Shortest path is required in situations like setting up a telecommunication network, transportation solutions, appointing a file server in a LAN, figuring out a flighting agenda.
4. Used in robotics to configure the most optimal path in drones and robots.
5. Used in computer networks for IP routing to find Open shortest Path first.

..and many more!

Disadvantages

Dijkstra has a major caveat- it wastes a lot of necessary time and resources because it does a blind search. Another problem is its inability to handle negative edges.

For Dijkstra algorithm to work, there are some specific guidelines that the problem must follow:

1. Graph must be connected

2. Graph can only contain non negative edge weights

Due to these above limitations, Dijkstra’s algorithm fails to provide the correct solution in the most prominent case of existence of negative edges. This is due to the fact that Dijkstra adds up the weights to get the most optimal path and it assumes that once a node has been visited, the path taken to get there is the shortest one. However, this may not be the case with negative weights as the total weight can be decremented afterwards.

This can be seen in the example below:

In the above problem, consider the path from A to B. Following the traditional Dijkstra approach, The path from A to B would have weight 3. However, if we consider the path A->D->C->B: the weight comes out to be -3, which is the better solution. Thus, Dijkstra sometimes fails in case of negative edge weights.

The solution

In case of the presence of negative edges, a better algorithm can be applied to get the correct answer- Bellman Ford. Bellman Ford is an implementation of dynamic programming and is simpler to apply than Dijkstra as well as well- suited to distributed systems. On first glance, the implementation of Bellman seems very similar to Dijkstra, however Bellman goes through every edge in every iteration as compared to Dijkstra- which only considers the vertices that are adjacent to the vertex being considered. Bellman thus runs through every edge V times to take care of the worst case in which the shortest distance would need to be adjusted v times. The complexity of Bellman Ford comes slightly higher than Dijkstra's being O(EV).

Conclusion

Dijkstra algorithm is thus a widely applied algorithm for figuring out the shortest path between vertices of a graph with a simple time complexity of O(E LogV).