A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

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 ...