9 Dijkstra’s algorithm
In this chapter
- We continue the discussion of graphs, and you learn about weighted graphs, a way to assign more or less weight to some edges.
- You learn Dijkstra’s algorithm, which lets you answer “What’s the shortest path to X?” for weighted graphs.
- You learn about negative-weight edges in graphs, where Dijkstra’s algorithm doesn’t work.
In chapter 6, you figured out a way to get from point A to point B.
It’s not necessarily the fastest path. It’s the shortest path because it has the least number of segments (three segments). But suppose you add travel times to those segments. Now you see that there’s a faster path. ...
Get Grokking Algorithms, Second 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.
