Responder 1:

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 una ruta 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 de este tipo, pero Prim y Kruskal tienen la garantía de encontrar uno de ellos. Para un vértice específico (por ejemplo, X), un árbol de ruta más corta es un árbol que abarca, de modo que la ruta de X a cualquier otro vértice es lo más corto posible (es decir, tiene el peso mínimo 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).

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 la ruta más corta:

  • 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 DC de borde, mientras que Dijkstra agrega AC o BC, porque las rutas A-C y A-B-C (ambas con una distancia total 30) son más cortas que la ruta A-B-D-C (distancia total 31).

¿Cuál es la diferencia entre los algoritmos de Dijkstra, Kruskal y Prim?


Responder 2:

Los tres algoritmos se usan para calcular diferentes cosas.

El algoritmo de Dijkstra se usa para calcular la distancia mínima desde un nodo a todos los demás nodos en un gráfico ponderado.

El algoritmo de Kruskal y Prim se utilizan para calcular el árbol de expansión mínimo.

Voy a hablar un poco sobre cómo estos dos algoritmos son diferentes.

Asumimos un N nodos, M bordes gráfico conectado no dirigido. Elegir entre ellos depende mucho de los valores de N, M y cuál es el formato en el que se proporciona su gráfico.

Kruskal

Comienza con un conjunto de N árboles. Cada árbol está compuesto por un nodo. En cada paso, elige un borde que conecta dos árboles diferentes. Esta ventaja es la que tiene el costo mínimo que aún no se ha elegido.

Para hacer esto, debe ordenar los bordes y luego realizar un seguimiento de los nodos que forman cada árbol. Para esto, es probable que desee utilizar una estructura de datos de conjunto disjunto.

Remilgado

Prim comienza desde un nodo arbitrario e intenta expandirse a otros nodos y agregarlos al árbol de expansión. Lo hace eligiendo siempre el nodo que se puede conectar a un nodo que ya está en el árbol por un borde de longitud mínima.

La principal dificultad es identificar el nodo que está más cerca de los que ya se agregaron en el árbol de expansión y puede hacerlo en O (log N) utilizando un montón.

Lo que presenté anteriormente es una simplificación de los algoritmos. Si desea obtener más detalles o entender por qué funcionan, intente revisar estos enlaces:

http: //faculty.washington.edu/dc ...

Algoritmo de Kruskal - Wikipedia



Responder 3:

Creo que puede descubrir fácilmente las diferencias entre estos tres si conoce el concepto básico de estos algoritmos.

Estoy compartiendo algunos enlaces con usted donde obtendrá toda la información sobre estos algoritmos.

Espero que te ayude. :)

Algoritmo de Dijkstra:

Algo de Prim: https://www.youtube.com/watch?v=ZtZaR7EcI5Y

Kruskal's Algo: https://www.youtube.com/watch?v=EjVHtpWkIho&t=426s