5SHORTEST PATHS IN WEIGHTED GRAPHS
This chapter generalizes what we learned in Chapter 4 about finding shortest paths. In Chapter 4, 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? Maybe there’s one slow move that takes 10 minutes, but there are also three fast moves that take only eight minutes in total. We might prefer the three fast moves, since they save us time.
In this chapter, we’ll learn Dijkstra’s algorithm for finding shortest paths in weighted graphs. We’ll use it to determine the number of mice ...
Get Algorithmic Thinking 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.
