Algoritmo de árbol recubridor mínimo de Jarník-Prim
Jarník–Prim minimum spanning tree algorithm
- Fecha
- 1930 (Jarník); redescubierto en 1957 (Prim) y 1959 (Dijkstra) · fiabilidad alta
- Lugar
- Praga, Checoslovaquia (actual Chequia)
- Autoría
- Vojtěch Jarník; redescubierto por Robert C. Prim (1957) y Edsger W. Dijkstra (1959)
- Ámbito
- Saber y símbolos
⚠️ Dato en discusión: las fuentes no coinciden.
Qué se descubrió
Jarník describió un método para hallar el árbol recubridor de coste mínimo de un grafo: partiendo de un vértice cualquiera, añade en cada paso la arista más barata que conecte el árbol con un vértice nuevo. Prim y luego Dijkstra lo redescubrieron de forma independiente.
El algoritmo se conoce indistintamente como de Jarník, de Prim, de Prim-Dijkstra o DJP por sus múltiples descubrimientos independientes; el trabajo original de Jarník (1930) pasó desapercibido en Occidente hasta mucho después.
A qué dio paso
- Optimización de redes de telecomunicaciones y transporte
- Base de algoritmos voraces (greedy) en teoría de grafos
- Comparación y combinación con el algoritmo de Kruskal (1956)