Lesson 25 — Ultimate: Dijkstra with path

Boss level: the route, not just the cost

To return the actual route, Dijkstra also records prev[v] = the node we came from on the cheapest way to v. At the end, start at the target and follow prev backwards to the start, then reverse the list.

# prev = {"B": "A", "C": "B", "D": "C"}
# D -> C -> B -> A, reversed: A, B, C, D

Why it matters: a navigation app that only says "it is 12 minutes away" is useless — you need the turns. Reconstructing a path from "came from" links is used in games, maps and puzzle solvers.