Today I am continuing on with my review of a book on programming algorithms. The book, “Grokking Algorithms, Second Edition” by Aditya Bhargava, is well worth a read if you haven’t studied algorithms or if you would like a refresher. In Part 8 I covered the set covering problem. Today I cover Dijkstra’s algorithm as applied to the shortest path problem, a reliable way to find the shortest route between two points in a graph, as long as there are no negative values in the path.

When we talk about solving the problem of the shortest path between two points in a graph, we are speaking the language of mathematics. In the real world, this problem can be applied many scenarios uch as finding the quickest route between two cities, finding the best route on a network, or figuring out the best series of trades to maximize profit in financial markets.

Imagine a trucking company that needs to ship goods between Seattle, WA, and Albuquerque, NM. The company is faced with the challenge of finding the most efficient route, accounting for distance, road conditions, traffic, weather, and other potential obstacles that could delay their trucks. By applying Dijkstra’s algorithm, the trucking company can determine the shortest path from Seattle to Albuquerque, optimizing delivery times and reducing costs.

Below is an implementation of Dijkstra’s Algorithm in JavaScript, along with a run of sample data that demonstrates how it works.

Keep in mind that Dijkstra’s Algorithm only works with non-negative values at each step in the path. In the case where there are negative weights, other algorithms like the Bellman-Ford algorithm would be more appropriate.

Have you ever routed a trip on your phone’s map system and started driving, only to find that the map offered you alternate routes during your trip? Navigation is an example of finding the shortest path in a dynamic system. Because traffic conditions can radically change travel times, maps monitor your progress and the road conditions in real time and offer updates if they see problems in the predicted best route. What that demonstrates is the need not just to be able to calculate the best route, but to understand when the calculated route may no longer be optimal due to changing conditions.