Dijkstra's Shortest Path
Finding the cheapest route through a weighted graph by always settling the nearest unsettled node next and relaxing the distances to its neighbours. Fewest hops and cheapest cost stop being the same answer once edges carry weights.
What a learner can do afterwards
- Run the algorithm on a small weighted graph, keeping the table of best-known distances
- Say why the nearest unsettled node can be fixed and never revised
- Give a graph where the fewest-hops route is not the cheapest route
1 · Read
Dijkstra finds the cheapest route from a start to everywhere else where weights are zero or positive. You keep a table of best known distances, zero for the start and infinity elsewhere, plus the set of unsettled nodes. Each round you settle the unsettled node with the smallest best known distance.
You settle a node by relaxing its edges: compare the route through it against each neighbour best distance and keep the smaller, rewriting the table each round. Hops can lie: two hops of 50 and 50 cost 100, while three hops of 10, 10 and 10 cost 30, so the longer hop route wins and you read the route back off the table.
A settled node is never revised, and you can trust that. Any rival route must leave the settled region through some unsettled node, and with no negative weights that detour already costs at least as much. Negative weights would break the promise, and plain breadth first search only counts hops, so it misses cheaper routes with more steps.
You reach for Dijkstra whenever fewest hops and cheapest cost can disagree. Keep the table tidy, mark each newly settled node, and never reopen a settled row.
Always settle the nearest unsettled node, relax its edges, and trust settled rows.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.