Shortest path algorithms are a family of algorithms designed to solve the shortest path problem. The shortest path problem is something most people have some intuitive familiarity with: given two points, A and B, what is the shortest path between them? In computer science, however, the shortest path problem can take different forms and so different algorithms are needed to be able to solve them all.
Shortest path algorithms have many applications. Mapping software like Google or Apple maps makes use of shortest path algorithms. They are also important for road network, operations, and logistics research. Shortest path algorithms are also very important for computer networks, like the Internet.
A variety of algorithms exist to solve these problems depending on the type of path network being used. A few most commonly used basic algorithms are given below.
The Bellman-Ford algorithm solves the single-source problem in the general case, where edges can have negative weights and the graph is directed.
Here is the link to a short video explaning the basics of Bellman-Ford Algorithm.
A very important application of Bellman Ford is to check if there is a negative cycle in the graph.
Time Complexity of Bellman Ford algorithm is relatively high - O (V.E).
Let's discuss an optimized algorithm that can achieve the same result in an efficient way.
Dijkstra's algorithm makes use of breadth-first search (which is not a single source shortest path algorithm) to solve the single-source problem. It does place one constraint on the graph: there can be no negative weight edges. However, for this one constraint, Dijkstra greatly improves on the runtime of Bellman-Ford.
Take a look at this short video for understanding how Dijkstra's algoritm works.
Time Complexity of Dijkstra's Algorithm is O (V2) but with min-priority queue it drops down to O (V + E.logV).
The Floyd-Warshall algorithm solves the all-pairs shortest path problem. It uses a dynamic programming approach to do so.
Check out this video for the basic concept behind this algorithm.
The biggest advantage of using this algorithm is that all the shortest distances between any 2 vertices could be calculated in O (V3) where V is the number of vertices in a graph.
While Floyd-Warshall works well for dense graphs (meaning many edges), Johnson's algorithm works best for sparse graphs (meaning few edges). In sparse graphs, Johnson's algorithm has a lower asymptotic running time compared to Floyd-Warshall, with a time complexity of O (E.V + V2.log2V).
Here is the link to a short video for learning about this algorithm.
Now that you are familiar with algorithms for finding the shortest path, here are a few problems, sorted according to difficulty, to test your skills. It is important to consider all the constraints and use the correct algorithm for getting an optimized and efficient solution.
Great work in completing the problems above! If you have any doubts in any of the algorithms feel free to discuss them on our Telegram group.
We hope you liked this tutorial, as we have more coming up, next week on Algorithms, Simplified.