Algoritmo de Prim
Algoritmo que construye, paso a paso, el árbol de menor coste que conecta todos los vértices de un grafo con aristas ponderadas.
- Año
- 1930
- Protagonistas
- Edsger Dijkstra, Robert C. Prim
- Sección
- Matemáticas
Historia
Un grafo es un conjunto de puntos (vértices) unidos por líneas (aristas), y cada línea puede llevar un peso, como una distancia o un coste. Un árbol recubridor mínimo es una selección de esas líneas que conecta todos los puntos sin formar ciclos y con la suma de pesos más baja posible. Encontrarlo tiene aplicaciones prácticas en el diseño de redes de telecomunicaciones, tuberías, carreteras o circuitos, donde interesa unir todo gastando lo mínimo. El algoritmo de Prim resuelve este problema con una idea sencilla: empezar en un vértice cualquiera y, en cada paso, añadir al árbol la conexión más barata que lleve de lo ya construido a un vértice todavía no incluido.
Antes de Prim existían otros procedimientos para el mismo problema, y el propio enfoque voraz, que elige en cada paso la opción local más barata, era conocido en la teoría de grafos. La primera formulación que suele citarse es la del matemático checo Vojtěch Jarník, publicada en 1930. Según la tradición, el procedimiento quedó poco difundido en su época. Más tarde, el informático Robert C. Prim lo redescubrió de forma independiente en 1957, y Edsger W. Dijkstra lo volvió a presentar en 1959. Por este recorrido de redescubrimientos el algoritmo aparece también con los nombres de Jarník, Prim-Dijkstra o DJP. Joseph Kruskal publicó en 1956 otro método para el mismo problema, y el algoritmo de Borůvka es un tercer camino conocido.
El funcionamiento básico consiste en mantener dos conjuntos de vértices: los que ya forman parte del árbol y los que todavía no. Para cada vértice pendiente se guarda el coste mínimo de conectarlo al árbol. En cada iteración se extrae el vértice pendiente con menor coste, se añade al árbol junto con la arista que lo une, y se actualizan los costes de sus vecinos. La elección de la estructura que guarda esos costes condiciona la eficiencia. Una lista simple obliga a recorrer todos los vértices en cada paso, con un tiempo proporcional al cuadrado del número de vértices. El uso de montículos o colas de prioridad redujo mucho ese tiempo, y con estructuras más sofisticadas, como el montículo de Fibonacci, el algoritmo se vuelve especialmente eficiente en grafos densos. Como punto débil, el algoritmo básico solo trabaja sobre grafos conexos; para grafos desconectados hay que aplicarlo por separado a cada componente.
Hoy el algoritmo de Prim se enseña como un modelo estándar de algoritmo voraz y se emplea en problemas de diseño de redes, agrupamiento de datos, análisis de imágenes y planificación de rutas de infraestructura. Su versión sobre montículos sigue siendo una referencia en libros de algoritmos, y su corrección se demuestra mediante un argumento de intercambio de aristas que garantiza que el resultado es siempre de coste mínimo.
Cronología
- 1930El matemático checo Vojtěch Jarník describe el procedimiento que hoy se conoce como algoritmo de Prim.
- 1956Joseph Kruskal publica otro método para hallar árboles recubridores mínimos, muy relacionado con este problema.
- 1957Robert C. Prim lo redescubre y lo publica de forma independiente.
- 1959Edsger W. Dijkstra lo vuelve a presentar, lo que da origen al nombre DJP.
Curiosidades y anécdotas
Muchos nombres para un mismo método
Por sus sucesivos redescubrimientos, el algoritmo se conoce también como algoritmo de Jarník, Prim-Dijkstra o DJP.
Edsger Dijkstra1930–2002 · Informática