Dijkstra
Algoritmo classico per il cammino minimo da una sorgente a tutti gli altri nodi di un grafo con pesi degli archi non negativi, di Edsger Dijkstra (1956, pubblicato nel 1959).
L'idea: si esplora il nodo con la distanza nota più bassa, si aggiornano i vicini e si ripete. Con un heap binario come coda di priorità: O((V+E) log V). Con un heap di Fibonacci: O(E + V log V), teoricamente più veloce, raramente nella pratica.
Alla base di tutto il routing dei GPS, di BGP/OSPF, dell'esplorazione dei grafi sociali e dei fantasmi di Pac-Man. Alternative: A* (con euristica, più rapido per una sola coppia), Bellman-Ford (pesi negativi), Floyd-Warshall (tutte le coppie).