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, directions from Santa Monica Blvd to Hollywood Blvd in Los Angeles, as demonstrated by the following screenshot:

This is a very common problem in our lives, and we will use apps such as Apple, or Google Maps, or 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, and the algorithm is called the shortest path. There are two algorithms that are very famous, which are Dijkstra's algorithm and the Floyd-Warshall algorithm, which we will cover in the next sections.

Dijkstra's algorithm

Dijkstra's algorithm is a greedy algorithm (you will learn more about greedy algorithms in Chapter 14, Algorithm Design...