Dijkstra
Classic algorithm for the shortest path from a source to all other nodes in a graph with non-negative edge weights — Edsger Dijkstra (1956, published 1959).
Idea: explore the node with the lowest known distance, update neighbours, repeat. With a binary heap as priority queue: O((V+E) log V). With a Fibonacci heap: O(E + V log V) — theoretically faster, rarely in practice.
Powers all GPS routing, BGP/OSPF routing, social-graph traversal, Pac-Man ghosts. Competitors: A* (with heuristic, faster for single-pair), Bellman-Ford (negative weights), Floyd-Warshall (all-pairs).