Why it matters
Every mapping app, network router, and pathfinding system uses Dijkstra or a variant. Understanding it opens up graph optimization problems.
The architecture
Maintain a distance estimate for each node, initially infinity except source (0). Repeatedly extract the unvisited node with the smallest distance; for each neighbor, relax (update distance if smaller path found through current node).
Priority queue (min-heap) makes 'extract min' efficient.
How it works end to end
Why non-negative weights: with negative weights, greedy extraction of minimum can miss shorter paths through later-processed nodes. Bellman-Ford handles negatives.
Priority queue variants: binary heap (standard), Fibonacci heap (better asymptotic, worse constants), pairing heap (practical middle ground).
A*: Dijkstra + heuristic. Goal-directed search that's faster on point-to-point pathfinding.