Level 4 · Graph AlgorithmsBUILD YOUR INTUITION
Dijkstra
Finalize the nearest unfinished vertex, then relax outgoing edges to improve tentative distances to other vertices.
THE MENTAL MODELWhen should this come to mind?
Finalize the nearest unfinished vertex, then relax outgoing edges to improve tentative distances to other vertices.
Nonnegative weighted routesMinimum travel timeSignal propagation What makes it work
Edge weights must be nonnegative. Handle unreachable vertices explicitly. The published small-graph lesson selects the next vertex with a linear scan.
When to choose something else
Negative edge weights invalidate finalization; unweighted edges can use BFS.
See the pattern in action
Change the input. Follow the state. Make it yours.