algorithm - kruskal - prim algoritmo
¿Cuál es la diferencia entre el algoritmo de Dijkstra y Prim? (6)
¿Puede alguien decirme la diferencia entre Prim''s algoritmos de Dijkstra''s y Prim''s ? Sé lo que hace cada uno de los algoritmos. Pero a mí me parecen iguales. El algoritmo de Dijkstra almacena una suma de los límites de costo mínimo, mientras que el algoritmo de Prim almacena a lo sumo un borde de costo mínimo. ¿No es esto lo mismo?
Ambos pueden implementarse usando exactamente el mismo algoritmo genérico de la siguiente manera:
Inputs:
G: Graph
s: Starting vertex (any for Prim, source for Dijkstra)
f: a function that takes vertices u and v, returns a number
Generic(G, s, f)
Q = Enqueue all V with key = infinity, parent = null
s.key = 0
While Q is not empty
u = dequeue Q
For each v in adj(u)
if v is in Q and v.key > f(u,v)
v.key = f(u,v)
v.parent = u
Para Prim, pase f = w(u, v) y para Dijkstra pase f = u.key + w(u, v) .
Otra cosa interesante es que, por encima de Generic, también se puede implementar Breadth First Search (BFS), aunque sería una exageración porque la costosa cola de prioridad no es realmente necesaria. Para convertir el algoritmo genérico por encima de BFS, pase f = u.key + 1 que es lo mismo que imponer todos los pesos a 1 (es decir, BFS proporciona el número mínimo de bordes necesarios para atravesar del punto A al B).
Intuición
Aquí hay una buena manera de pensar sobre el algoritmo genérico anterior: comenzamos con dos cubos A y B. Inicialmente, ponga todos sus vértices en B para que el compartimiento A esté vacío. Luego, movemos un vértice de B a A. Ahora mire todos los bordes de los vértices en A que se cruzan sobre los vértices en B. Elegimos un borde usando algunos criterios de estos bordes cruzados y movemos el vértice correspondiente de B a A. Repita este proceso hasta que B esté vacío.
Una forma de fuerza bruta para implementar esta idea sería mantener una cola de prioridad de los bordes para los vértices en A que cruza a B. Obviamente eso sería problemático si el gráfico no fuera escaso. Entonces, la pregunta sería: ¿podemos mantener la cola de prioridad de los vértices? Esto, de hecho, podemos como nuestra decisión finalmente es qué vértice escoger de B.
Contexto histórico
Es interesante que la versión genérica de la técnica detrás de ambos algoritmos sea conceptualmente tan antigua como la de 1930, incluso cuando las computadoras electrónicas no existían.
La historia comienza con Otakar Borůvka, que necesitaba un algoritmo para un amigo de la familia que intentaba descubrir cómo conectar ciudades en el país de Moravia (ahora parte de la República Checa) con un costo mínimo de líneas eléctricas. Publicó su algoritmo en 1926 en una revista relacionada con las matemáticas, ya que Computer Science no existía en ese momento. Esto llamó la atención de Vojtěch Jarník, quien pensó en una mejora en el algoritmo de Borůvka y lo publicó en 1930. De hecho, descubrió el mismo algoritmo que ahora conocemos como el algoritmo de Prim que lo redescubrió en 1957.
Independientemente de todo esto, en 1956 Dijkstra necesitaba escribir un programa para demostrar las capacidades de una nueva computadora que su instituto había desarrollado. Pensó que sería genial tener una computadora que encuentre conexiones para viajar entre dos ciudades de los Países Bajos. Diseñó el algoritmo en 20 minutos. Creó una gráfica de 64 ciudades con algunas simplificaciones (porque su computadora era de 6 bits) y escribió el código para esta computadora de 1956. Sin embargo, no publicó su algoritmo porque principalmente no había revistas de informática y pensó que esto podría no ser muy importante. Al año siguiente, se enteró del problema de conectar terminales de computadoras nuevas de tal manera que se minimizase la longitud de los cables. Pensó en este problema y volvió a descubrir el algoritmo de Jarník / Prim, que nuevamente usa la misma técnica que el algoritmo de ruta más corta que había descubierto un año antes. mentioned que sus dos algoritmos fueron diseñados sin usar lápiz o papel. En 1959, publicó ambos algoritmos en un paper solo 2 páginas y media.
El algoritmo de Dijkstra es un problema de ruta más corta de una sola fuente entre los nodos i y j, pero el algoritmo de Prim es un problema de árbol de expansión mínimo. Estos algoritmos utilizan el concepto de programación llamado ''algoritmo codicioso''
Si marca esta noción, por favor visite
- Nota de conferencia sobre el algoritmo codicioso: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-greedy.pdf
- Árbol de expansión mínimo: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/20-mst.pdf
- La ruta más corta de una sola fuente: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/21-sssp.pdf
El algoritmo de Dijsktra encuentra la distancia mínima desde el nodo i a todos los nodos (usted especifica i). Entonces, a cambio, obtienes el árbol de distancia mínima del nodo i.
El algoritmo Prims le proporciona el árbol de expansión mínimo para un gráfico dado . Un árbol que conecta todos los nodos, mientras que la suma de todos los costos es el mínimo posible.
Así que con Dijkstra puede pasar del nodo seleccionado a cualquier otro con el costo mínimo , no puede obtener esto con Prim''s
La única diferencia que veo es que el algoritmo de Prim almacena un margen de costo mínimo, mientras que el algoritmo de Dijkstra almacena el costo total desde un vértice de origen hasta el vértice actual.
Dijkstra le ofrece un camino desde el nodo de origen al nodo de destino, de modo que el costo sea mínimo. Sin embargo, el algoritmo de Prim le da un árbol de expansión mínimo de tal manera que todos los nodos están conectados y el costo total es mínimo.
En palabras simples:
Por lo tanto, si desea implementar un tren para conectar varias ciudades, debe usar algo de Prim. Pero si quieres ir de una ciudad a otra ahorrando tanto tiempo como sea posible, usarías algo de Dijkstra.
La explicación más sencilla es que en Prims no especifica el nodo de inicio , pero en dijsktra (necesita tener un nodo de inicio) debe encontrar la ruta más corta desde el nodo dado a todos los demás nodos.
Me molestó la misma pregunta últimamente, y creo que podría compartir mi entendimiento ...
Creo que la diferencia clave entre estos dos algoritmos (Dijkstra y Prim) radica en el problema que están diseñados para resolver, es decir, la ruta más corta entre dos nodos y el árbol de expansión mínimo (MST). Lo formal es encontrar la ruta más corta entre, por ejemplo, los nodos s y t , y un requisito racional es visitar cada borde de la gráfica como máximo una vez. Sin embargo, NO requiere que visitemos todo el nodo. El último (MST) es hacer que visitemos TODO el nodo (como máximo una vez), y con el mismo requisito racional de visitar cada borde como máximo una vez.
Dicho esto, Dijkstra nos permite "tomar atajos" siempre que pueda pasar de un lado a otro, sin preocuparme por las consecuencias: una vez que llegue a t , ¡ya terminé! Aunque también hay una ruta desde s hasta t en la MST, pero esta ruta s - t se crea con consideraciones de todos los nodos restantes, por lo tanto, esta ruta puede ser más larga que la ruta s - t encontrada por el algoritmo de Dijstra. A continuación se muestra un ejemplo rápido con 3 nodos:
2 2
(s) o ----- o ----- o (t)
| |
-----------------
3
Digamos que cada uno de los bordes superiores tiene un costo de 2, y el borde inferior tiene un costo de 3, entonces Dijktra nos dirá cuál es el camino inferior, ya que no nos importa el nodo central. Por otro lado, Prim nos devolverá un MST con los 2 bordes superiores, descartando el borde inferior.
Dicha diferencia también se refleja en la sutil diferencia en las implementaciones: en el algoritmo de Dijkstra, se necesita tener un paso de contabilidad (para cada nodo) para actualizar el camino más corto desde s , después de absorber un nuevo nodo, mientras que en el algoritmo de Prim, hay No existe tal necesidad.