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, and the algorithm is called the shortest path. There are two algorithms that are very famous, which are Dijkstra's algorithm and Floyd-Warshall algorithm, which we will cover in the next topics.
Dijkstra's algorithm
Dijkstra's algorithm is a greedy algorithm (you will learn more about greedy algorithms in Chapter 11 , Patterns of Algorithm ) to calculate...