Dijkstra
Algoritmo clásico para el camino más corto desde un origen a todos los demás nodos de un grafo con pesos no negativos: Edsger Dijkstra lo ideó en 1956 y lo publicó en 1959.
La idea es sencilla: explora el nodo con la menor distancia conocida, actualiza sus vecinos y repite. Con un montículo binario como cola de prioridad sale O((V+E) log V); con un montículo de Fibonacci, O(E + V log V), teóricamente mejor y en la práctica casi nunca.
Está detrás de todo el enrutado GPS, del cálculo de rutas en BGP y OSPF, del recorrido de grafos sociales y hasta de los fantasmas del Pac-Man. Alternativas: A* (con heurística, más rápido para un solo destino), Bellman-Ford (admite pesos negativos) y Floyd-Warshall (todos contra todos).