Shortest Path Problem in Search of Algorithmic Solution
The shortest path problem at its core is very simple; find the shortest path between two nodes, or vertices, in a graph while accounting for the weight of the connecting edges. There are an ever-growing number of solutions to this problem. In fact, once you understand search algorithms there is no reason why you couldn’t write your own search algorithm. In the meantime, it might just be best to use tried and tested algorithms that are known to work, and known to work well.
This list is not at all comprehensive. There is a nearly inexhaustible list of search algorithms that exist if you account for adding heuristics to to them. A heuristic is a function that modifies the algorithm to help provide an adequate solution at a faster pace. I say adequate, because what you make up in time you lose in accuracy. Sometimes a heuristic will modify a search algorithm to get you a solution that is very close to optimal, but isn’t optimal. However, for certain situations, such as non-playable character movement in a video game, decreased runtime is worth the sacrifice in accuracy since memory is at a premium.
The shortest path problem has two main was of being solved. The single-source method has the algorithm search for the shortest path between the start node and end node (or any two nodes for that matter), and the algorithm stops once the shortest path is found. The other method type is the all-pairs method. All-pairs algorithms return a matrix of values that are all the shortest paths from one node to another node.
The Algorithms
Dijkstra’s Algorithm
The grandfather of all search algorithms. Dijkstra’s has many variants and is the base for many other algorithms. This algorithm uses a breadth-first search (BFS) to traverse a graph and find the shortest path. While a BFS is not a single-source algorithm, Dijkstra’s implements it in a way to solve the single-source version of the shortest path problem. The BFS traverses a graph by visiting every node and edge in a well-defined order and marking each node along the way. Dijkstra’s algorithm cannot have edges with a negative weight.
Dijkstra’s algorithm has a time complexity of O(|E|+|V|log|V|), or O(|V |²) when using an array.
Bellman-Ford Algorithm
The Bellman-Ford algorithm is a single-source algorithm used to find the shortest path from the start node to the end node, or any other node for that matter, in a weighted graph. This algorithm uses the observation that the shortest path must include, at most, V-1 edges, since a shortest path can never be part of a cycle. This algorithm overestimates the path from the starting node to all other nodes by setting it to infinity, and then it iterates over the graph ‘relaxing’ the estimate to a new smaller value. Bellman-Ford visits all nodes adjacent to the start node and relaxes their distances from infinity to their true value. It then iterates over the next outer loop checking their adjacent nodes and relaxing their distances. It does this until all nodes have been visited and all edges relaxed. The result is an optimized distance to each node from the start node.
The Bellman-Ford algorithm has a time complexity of O(|V|⋅|E|).
Floyd-Warshall Algorithm
The Floyd-Warshall algorithm is an algorithm used to solve the all-pairs version of shortest path problem, and it is probably the most common algorithm used in this manner. It works very quickly to find the shortest path between all pairs of nodes. It also allows for both positive and negative edge weights. The algorithm works by first initializing all path distances between nodes to infinity. It then finds all shortest paths that don’t involve the use of an intermediate node. Next it finds every shortest path that only uses one intermediate node, and so-on, until it reaches the point of using N-nodes as intermediates. Next it minimizes the path distance by iterating through all the paths from the previous step to find the optimal shortest path.
Floyd-Warshall algorithm has a time complexity of O(|V|³).
A* Algorithm
A* algorithm, pronounces ‘A-star’, is a best-first search algorithm. A best-first search algorithm, often called a greedy algorithm, is an algorithm that makes optimal local choices in pursuit of an optimal global path. For instance, when choosing which edge to traverse next the algorithm will always choose the edge with the smallest weight. A* works by building a tree of paths that begin at the start node and end once a specific criteria is met. Some branches will prove to never be able to be the shortest path, so they are discontinued. When selecting which edge to traverse next, a heuristic is used to determine how to queue each adjacent node. The nodes are prioritized based on their weight, smallest being considered most likely to provide an optimal solution. The node with the smallest edge weight is checked, its nodes are queued up, and the process continues. Once the end node is located, the sequence of traversals can be reversed in order to point back at the start node. A* will always find the solution. One drawback to the A* algorithm is that it has a large space complexity. It requires added memory to build its traversal tree.
A* algorithm has a time complexity of O(|E|).
