Learning JavaScript Data Structures and Algorithms - Second Edition

Shortest path algorithms

Given a map of streets, consider you want to get from point A to point B using the shortest path possible. We can use, as an example for this problem, the way from Santa Monica Blvd to Hollywood Blvd in Los Angeles, as demonstrated by the following image:

This is a very common problem in our lives, and we will use apps such as Apple or Google Maps and Waze to try to solve it, especially if you live in a big city. Of course, we also have other constraints involved, such as time or car traffic, but the original problem remains: how do we get from A to B using the shortest path?

We can use graphs to solve this problem for us, ...