III · Graph theory
Shortest paths
What it is
Dijkstra: O((V + E) log V) with a binary heap. Bellman-Ford: O(V·E), handles negative edges. A*: Dijkstra with an admissible heuristic.
Where it lives
Routing protocols (OSPF), GPS navigation, project scheduling, network distance in CDNs.
The key insight
A heuristic h(n) is admissible if h(n) ≤ true cost from n to goal. With one, A* expands O(b^d) nodes instead of all reachable.