Camino más corto de Dijkstra

El algoritmo de Dijkstra encuentra el camino más corto entre nodos de un grafo con pesos no negativos. Funciona de manera voraz (greedy) y actualiza las distancias mediante relajación: d(v) = min(d(v), d(u) + w(u,v)). Su complejidad se optimiza a O(E + V log V) usando colas de prioridad de montículo de Fibonacci.

Dijkstra hace crecer una frontera desde el nodo inicial y siempre fija el nodo no visitado que está más cerca. Como todo peso de arista es no negativo, ningún desvío posterior puede mejorar una ruta más corta ya encontrada: una vez fijado un nodo, su distancia es definitiva y no se vuelve a revisar. Por eso los planificadores de rutas y protocolos de enrutamiento como OSPF confían en él para calcular caminos mínimos fiables.

Edsger Dijkstra concibió el algoritmo en 1956 en unos veinte minutos, sin lápiz ni papel, mientras descansaba en la terraza de un café de Ámsterdam. Buscaba un problema de demostración para el ordenador ARMAC y eligió la ruta más corta entre dos ciudades neerlandesas, Róterdam y Groninga. Lo publicó tres años después en un artículo de apenas tres páginas, uno de los resultados más citados de la informática.