Dijkstra
Klassisk algoritm för kortaste vägen från en startnod till alla andra i en graf med icke-negativa kantvikter — Edsger Dijkstra (1956, publicerad 1959).
Tankesätt: utforska noden med lägsta känt avstånd, uppdatera grannar, upprepa. Med binär heap som priority queue: O((V+E) log V). Med Fibonacci heap: O(E + V log V) — teoretiskt snabbare men sällan i praktiken.
Driver alla GPS-rutter, BGP/OSPF-routing, social-graf-traversal, Pac-Man-spöken. Konkurrenter: A* (med heuristik, snabbare för en-paret), Bellman-Ford (negativa vikter), Floyd-Warshall (all-pairs).