Most people are aware of the shortest path problem, but their familiarity with it begins and ends with considering the shortest path between two points, A and B. However, for computer scientists this problem takes a different turn, as different algorithms may be needed to solve the different problems.

For simplicity, shortest path algorithms operate on a graph, which is made up of vertices and edges that connect them. A graph may be directed, indirected, weighted, and more. It’s these distinctions that determine which algorithm will work better than another for certain graph types.

Shortest path algorithms have various uses, most notable being Route planning software such as Google Maps, and us – here at MyRouteOnline we make use of shortest path algorithms to generate your routes.

As there are a number of different shortest path algorithms, we’ve gathered the most important to help you understand how they work and which is the best.

Dijkstra’s Algorithm stands out from the rest due to its ability to find the shortest path from one node to every other node within the same graph data structure. This means, that rather than just finding the shortest path from the starting node to another specific node, the algorithm works to find the shortest path to every single reachable node – provided the graph doesn’t change.

The algorithm runs until all of the reachable nodes have been visited. Therefore, you would only need to run Dijkstra’s algorithm once, and save the results to be used again and again without re-running the algorithm – again, unless the graph data structure changed in any way.

In the case of a change in the graph, you would need to rerun the graph to ensure you have the most updated shortest paths for your data structure.

Let’s take our routing example from above, if you want to go from A to B in the shortest way possible, but you know that some roads are heavily congested, blocked, undergoing works, and so on, when using Dijkstra, the algorithm will find the shortest path while avoiding any edges with larger weights, thereby finding you the shortest route.

Similar to Dijkstra’s algorithm, the Bellman-Ford algorithm works to find the shortest path between a given node and all other nodes in the graph. Though it is slower than the former, Bellman-Ford makes up for its a disadvantage with its versatility. Unlike Dijkstra’s algorithm, Bellman-Ford is capable of handling graphs in which some of the edge weights are negative.

It’s important to note that if there is a negative cycle – in which the edges sum to a negative value – in the graph, then there is no shortest or cheapest path. Meaning the algorithm is prevented from being able to find the correct route since it terminates on a negative cycle. Bellman-Ford is able to detect negative cycles and report on their existence.

The Floyd-Warshall stands out in that unlike the previous two algorithms it is not a single-source algorithm. Meaning, it calculates the shortest distance between every pair of nodes in the graph, rather than only calculating from a single node. It works by breaking the main problem into smaller ones, then combines the answers to solve the main shortest path issue.

Floyd-Warshall is extremely useful when it comes to generating routes for multi-stop trips as it calculates the shortest path between all the relevant nodes. For this reason, many route planning software’ will utilize this algorithm as it will provide you with the most optimized route from any given location. Therefore, no matter where you currently are, Floyd-Warshall will determine the fastest way to get to any other node on the graph.

Johnson’s algorithm works best with sparse graphs – one with fewer edges, as it’s runtime depends on the number of edges. So, the fewer edges, the faster it will generate a route.

This algorithm varies from the rest as it relies on two other algorithms to determine the shortest path. First, it uses Bellman-Ford to detect negative cycles and eliminate any negative edges. Then, with this new graph, it relies on Dijkstra’s algorithm to calculate the shortest paths in the original graph that was inputted.

More often than not, the best algorithm to use won’t be left up to you to decide, rather it will be dependant upon the type of graph you are using and the shortest path problem that is being solved. For example, for problems with negative weight edges, you would turn to Bellman-Ford, whereas for sparse graphs with no negative edges you would turn to Dijsktra’s algorithm.

When it comes down to it, many aspects of these algorithms are the same, however, when you look at performance and use, that’s where the differences come to light. Therefore, rather than asking which algorithm is the best, you should consider which is the right one for the type of graph you are operating on and shortest path problem you are trying to solve.

How to Adjust to Driving on the ‘Opposite’ Side of the Road
December 17, 2018

Celebrate National Truck Driver Appreciation Week!
September 09, 2016