Computer scienceAlgorithms and Data StructuresAlgorithmsGraph algorithmsShortest path algorithms

Comparing the shortest path algorithms

Provided by: JetBrains Academy
7 minutes read

As you already know, the shortest path problem plays a fundamental role in computer science. It has numerous applications: for example, mapping apps, like Google or Apple maps, make use of shortest path algorithms and solve the problem for you. These algorithms are also important for computer and road networks, operations, and logistics research. Unexpectedly, they also come in handy in other areas, such as economics or even natural sciences.

In this topic, we will briefly recap the features and limitations of each algorithm. This will help us understand how to always choose the right tool in all kinds of situations.

SSSP

The single-source shortest path problem consists in finding the shortest paths from the source node to all other nodes in a weighted graph with nn nodes and mm edges. The most common tools for solving this task are the Dijkstra and Bellman-Ford algorithms. Their goal is the same; however, there are significant differences between them as shown in the table below:

single-source shortest path problem

In the case of sparse graphs, where m≈nm\approx n, the time complexity of the Bellman-Ford algorithm will be O(n2)O(n^2), whereas Dijkstra's algorithm will take O(nlog⁡n)O(n\log n) time if implemented using a binary heap. On the other hand, if the graph is dense, i.e., m≈n2m \approx n^2, the Bellman-Ford algorithm is inefficient, as it takes O(n3)O(n^3) steps to complete its job. The array implementation of Dijkstra's algorithm is considerably faster, as it uses O(n2)O(n^2) time.

All-pairs shortest path

One has to simply take a look at its name to tell that the all-pairs shortest path problem asks us to find the shortest paths between all pairs of nodes in a weighted graph with nn nodes and mm edges. This is an instance of MSSP and is usually solved with the help of the Floyd-Warshall or Johnson's algorithm. Johnson's algorithm is quite fast; meanwhile, Floyd-Warshall is often preferred due to the fact that it can be easily implemented. Additional information is provided in the table.

All-pairs shortest path problem

For sparse graphs, Johnson's algorithm takes O(n2log⁡n)O(n^2\log n) time, which is faster than Floyd-Warshall. However, if the graph is dense, both algorithms have the same time complexity, namely O(n3)O(n^3).

Maze-Routing

Determining the path between two cells in a n×mn \times m maze is a classic problem in computer science. Lee's algorithm doesn't simply return some arbitrary path between the cells – it finds the shortest path. This task is known as the maze-routing problem.

maze-routing problem

Conclusion

Here is a short summary of the uses of the above algorithms.

  • Dijkstra's algorithm should be applied if you are trying to solve the SSSP problem and the graph contains no negative edges. Furthermore, if the graph is dense, use the array implementation. Otherwise, the binary heap implementation is considerably faster.
  • The Bellman-Ford algorithm should be used if you are trying to solve the SSSP problem and the graph contains negative edges.
  • Johnson's algorithm is preferable if you want to solve the all-pairs shortest path problem and the graph is sparse.
  • The Floyd-Warshall algorithm may be used if you are too lazy to implement Johnson's algorithm.
  • Lee's algorithm is the right choice if you intend to solve the maze-routing problem.

After some practice, making the optimal decision on shortest path algorithms should be as easy as taking candy from a baby.

6 learners liked this piece of theory. 0 didn't like it. What about you?
Report a typo