¿Cuál es la diferencia entre los algoritmos de Dijkstra, Kruskal y Prim?
La primera distinción es que el algoritmo de Dijkstra resuelve un problema diferente al de Kruskal y Prim. Dijkstra resuelve el problema de la ruta más corta (desde un nodo específico), mientras que Kruskal y Prim encuentran un árbol de expansión de costo mínimo. La siguiente es una forma modificada de una descripción que escribí en esta página: Algoritmos gráficos.
- Para cualquier gráfico, un árbol de expansión es una colección de bordes suficiente para proporcionar exactamente un camino entre cada par de vértices. Esta restricción significa que no puede haber circuitos formados por los bordes elegidos.
- Un árbol de expansión de costo mínimo es aquel que tiene el peso total más pequeño posible (donde el peso representa el costo o la distancia). Puede haber más de un árbol, pero Prim y Kruskal tienen la garantía de encontrar uno de ellos.
- Para un vértice especificado (digamos X), un árbol de ruta más corta es un árbol de expansión de manera que la ruta desde X a cualquier otro vértice es lo más corta posible (es decir, tiene el mínimo peso posible).
Prim y Dijkstra “hacen crecer” el árbol desde un vértice inicial. En otras palabras, tienen un enfoque “local”; En cada paso, solo consideramos aquellos bordes adyacentes a los vértices elegidos previamente, eligiendo la opción más barata que satisfaga nuestras necesidades. Mientras tanto, Kruskal es un algoritmo “global”, lo que significa que cada borde se elige (con avidez) de todo el gráfico. (En realidad, podría considerarse que Dijkstra tiene algún aspecto global, como se indica a continuación).
- Cómo encontrar el factorial de un número grande, como 100, en C
- ¿Cuál es la aplicación en tiempo real de árboles y gráficos en estructuras de datos?
- ¿Dónde se usa la cola prioritaria?
- ¿Qué significa si un futuro programador apesta u odia los algoritmos de aprendizaje y las estructuras de datos?
- ¿Debería un algoritmo de aprendizaje automático estar completo?
Para encontrar un árbol de expansión de costo mínimo:
- Kruskal (enfoque global): en cada paso, elija el borde más barato disponible en cualquier lugar que no viole el objetivo de crear un árbol de expansión.
- Prim (enfoque local): elija un vértice inicial. En cada paso sucesivo, elija la arista disponible más barata adjunta a cualquier vértice elegido previamente que no viole el objetivo de crear un árbol de expansión.
Para encontrar un árbol de expansión de camino más corto:
- Dijkstra: en cada paso, elija el borde adjunto a cualquier vértice previamente elegido (el aspecto local) que hace que la distancia total desde el vértice inicial (el aspecto global) sea lo más pequeña posible, y no viola el objetivo de crear un árbol de expansión .
Los árboles de costo mínimo y los árboles de camino más corto se confunden fácilmente, al igual que los algoritmos Prim y Dijkstra que los resuelven. Ambos algoritmos “crecen” desde el vértice inicial, en cada paso eligiendo un borde que conecta un vértice Y que está en el árbol con un vértice Z que no lo está. Sin embargo, mientras Prim elige el borde más barato, Dijkstra elige el borde que da como resultado el camino más corto de X a Z.
Una ilustración simple es útil para comprender la diferencia entre estos algoritmos y los árboles que producen. En el gráfico a continuación, comenzando desde el vértice A, tanto Prim como Dijkstra comienzan eligiendo el borde AB y luego agregando el borde BD. Aquí es donde los dos algoritmos divergen: Prim completa el árbol agregando el borde DC, mientras que Dijkstra agrega AC o BC, porque los caminos AC y ABC (ambos con una distancia total de 30) son más cortos que el camino ABDC (distancia total 31).
