5SHORTEST PATHS IN WEIGHTED GRAPHS

Image

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 O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.