6SHORTEST PATHS IN WEIGHTED GRAPHS
This chapter generalizes what we learned in Chapter 5 about finding shortest paths. In Chapter 5, our focus was on finding the minimum number of moves needed to solve a problem. Now, what if we care not about the minimum number of moves but about the minimum amount of time or distance? Think about using a GPS app to get home. Maybe there’s a route to get home using only one street that takes 10 minutes. Maybe there’s another way that involves using three streets that takes only eight minutes in total. We might prefer using the three streets, since they save us time.
In this chapter, we’ll learn Dijkstra’s algorithm ...
Get Algorithmic Thinking, 2nd Edition 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.
