Dijkstra’s Algorithm
Numerous algorithms can solve the shortest path problem, and one of the most famous is one discovered by Edsger Dijkstra (pronounced “dike’ struh”) in 1959. Unsurprisingly, this algorithm is known as Dijkstra’s algorithm.
In this section, we’re going to use Dijkstra’s algorithm to find the cheapest path in our city flights example.
Dijkstra’s Algorithm Setup
The first thing to note is that Dijkstra’s algorithm comes with a free bonus. By the time we’re done, we’re not just going to find the cheapest price from Atlanta to El Paso, but also we’re going to find the cheapest prices from Atlanta to all known cities. As you’ll see, the algorithm simply works this way; we end up gathering all of this data. So we’ll know the cheapest ...
Get A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1 now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
