Algoritmo de Dijkstra de caminos mínimos

Qué se descubrió

Algoritmo eficiente que halla el camino de menor coste desde un origen a todos los nodos de un grafo con pesos no negativos. Prototipo de algoritmo voraz y pieza central de la algoritmia.

Dijkstra lo ideó en veinte minutos en una terraza de café pensando en el mapa de los Países Bajos.

A qué dio paso

• algoritmia y análisis de algoritmos
• A* y búsqueda heurística
• protocolos de enrutamiento (OSPF)

Se apoya en

• Teoría de grafos: los siete puentes de Königsberg1736
• programación dinámica de Bellman

Hizo posible

• Algoritmo de Floyd-Warshall1959-1962
• Algoritmo de búsqueda A*1968
• Navegador de automóvil (Electro Gyrocator, Etak, Mazda GPS)1981-1990
• Algoritmo de la colonia de hormigas1992
• navegadores GPS
• enrutamiento en internet
• planificación de robots

📄 Publicación original

Enlaces