Dijkstra’s Algorithm: A Critical Review

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.

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.

Pseudo Code

A Practical Demonstration

Actual Implementation

Output of above Code

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.

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.

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.

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).

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store