¿Diferencia entre los algoritmos de Prim y Dijkstra?

¿Cuál es la diferencia exacta entre los algoritmos de Dijkstra y Prim? Sé que Prim dará un MST, pero el árbol generado por Dijkstra también será un MST. Entonces, ¿cuál es la diferencia exacta?

El algoritmo de Prim construye un árbol de expansión mínimo para el gráfico, que es un árbol que conecta todos los nodos del gráfico y tiene el menor costo total entre todos los árboles que conectan todos los nodos. Sin embargo, la longitud de una ruta entre dos nodos en el MST podría no ser la ruta más corta entre esos dos nodos en el gráfico original. Los MST son útiles, por ejemplo, si desea conectar físicamente los nodos en el gráfico para proporcionarles electricidad al menor costo total. No importa que la longitud de la ruta entre dos nodos no sea la óptima, ya que lo único que le importa es el hecho de que están conectados.

El algoritmo de Dijkstra construye un árbol de ruta más corto a partir de algún nodo fuente. Un árbol de ruta más corto es un árbol que conecta todos los nodos en el gráfico con el nodo de origen y tiene la propiedad de que la longitud de cualquier ruta desde el nodo de origen a cualquier otro nodo en el gráfico se minimiza. Esto es útil, por ejemplo, si desea construir una red de carreteras que lo haga lo más eficiente posible para que todos lleguen a un hito importante. Sin embargo, no se garantiza que el árbol de la ruta más corta sea un árbol de expansión mínimo, y la suma de los costos en los bordes de un árbol de la ruta más corta puede ser mucho mayor que el costo de un MST.

Otra diferencia importante se refiere a los tipos de gráficos en los que trabajan los algoritmos. El algoritmo de Prim solo funciona en gráficos no dirigidos, ya que el concepto de un MST asume que los gráficos son inherentemente no dirigidos. (Existe algo llamado "arborescencia de expansión mínima" para gráficos dirigidos, pero los algoritmos para encontrarlos son mucho más complicados). El algoritmo de Dijkstra funcionará bien en gráficos dirigidos, ya que de hecho se pueden dirigir los árboles de ruta más corta. Además, el algoritmo de Dijkstra no necesariamente produce la solución correcta en gráficos que contienen pesos de borde negativos , mientras que el algoritmo de Prim puede manejar esto.

¡Espero que esto ayude!

El algoritmo de Dijkstra no crea un MST, encuentra el camino más corto.

Considere este gráfico

       5     5
  s *-----*-----* t
     \         /
       -------
         9

El camino más corto es el 9, mientras que el MST es un 'camino' diferente en el 10.

Los algoritmos de Prim y Dijkstra son casi iguales, excepto por la "función de relajación".

Remilgado:

MST-PRIM (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v)    <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

Dijkstra:

Dijkstra (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v) + u.key  <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

La única diferencia la señala la flecha, que es la función de relajación.

• El Prim, que busca el árbol de expansión mínimo, solo se preocupa por el mínimo de los bordes totales que cubren todos los vértices. La función relax esalt = w(u,v)
• El Dijkstra, que busca la longitud mínima del camino, se preocupa por la acumulación de bordes. La función de relajación esalt = w(u,v) + u.key

El algoritmo de Dijsktra encuentra la distancia mínima desde el nodo i hasta todos los nodos (usted especifica i). Entonces, a cambio, obtienes el árbol de distancia mínima desde el nodo i.

El algoritmo de Prims le proporciona el árbol de expansión mínimo para un gráfico determinado . Un árbol que conecta todos los nodos mientras que la suma de todos los costos es la mínima posible.

Entonces con Dijkstra puedes pasar del nodo seleccionado a cualquier otro con el costo mínimo , esto no lo obtienes con Prim's

La única diferencia que veo es que el algoritmo de Prim almacena una ventaja 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 brinda un camino desde el nodo de origen al nodo de destino de manera que el costo sea mínimo. Sin embargo, el algoritmo de Prim le brinda un árbol de expansión mínimo, de modo que todos los nodos están conectados y el costo total es mínimo.

En palabras simples:

Entonces, si desea desplegar un tren para conectar varias ciudades, usaría el algoritmo de Prim. Pero si desea ir de una ciudad a otra ahorrando el mayor tiempo posible, usaría el algoritmo de Dijkstra.

Ambos se pueden implementar utilizando 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 excesivo porque la cola de prioridad costosa no es realmente necesaria. Para convertir el algoritmo genérico anterior en BFS, pase lo f = u.key + 1que equivale a aplicar todos los pesos a 1 (es decir, BFS da el número mínimo de bordes necesarios para atravesar desde el punto A al B).

Intuición

Aquí hay una buena manera de pensar en el algoritmo genérico anterior: comenzamos con dos cubos A y B. Inicialmente, coloque todos sus vértices en B para que el cubo A esté vacío. Luego, movemos un vértice de B a A. Ahora mire todas las aristas de los vértices en A que cruzan a los vértices en B. Elegimos una arista usando algunos criterios de estas aristas cruzadas 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 cruzan 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 vértices? Esto, de hecho, podemos decidir finalmente qué vértice elegir 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 1930, incluso cuando no existían computadoras electrónicas.

La historia comienza con Otakar Borůvka, quien necesitaba un algoritmo para un amigo de la familia que intentaba averiguar cómo conectar ciudades en el país de Moravia (ahora parte de la República Checa) con líneas eléctricas de costo mínimo. Publicó su algoritmo en 1926 en una revista relacionada con las matemáticas, ya que la informática no existía entonces. 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 y lo redescubrió en 1957.

Independientemente de todo esto, en 1956 Dijkstra necesitaba escribir un programa para demostrar las capacidades de una nueva computadora que había desarrollado su instituto. Pensó que sería genial que una computadora encontrara conexiones para viajar entre dos ciudades de los Países Bajos. Diseñó el algoritmo en 20 minutos. Creó un gráfico de 64 ciudades con algunas simplificaciones (porque su computadora era de 6 bits) y escribió 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 modo que se minimizara la longitud de los cables. Pensó en este problema y redescubrió a Jarník / Prim ' s que utiliza de nuevo la misma técnica que el algoritmo de ruta más corta que había descubierto un año antes. Élmencionó que ambos algoritmos fueron diseñados sin usar lápiz o papel. En 1959 publicó ambos algoritmos en un artículo de tan solo dos páginas y media.

Dijkstra encuentra la ruta más corta entre su nodo inicial y cualquier otro nodo. Entonces, a cambio, obtiene el árbol de distancia mínima desde el nodo inicial, es decir, puede llegar a cualquier otro nodo de la manera más eficiente posible.

El algoritmo de Prims le proporciona el MST para un gráfico dado, es decir, un árbol que conecta todos los nodos mientras que la suma de todos los costos es la mínima posible.

Para hacer una historia corta con un ejemplo realista:

1. Dijkstra quiere conocer el camino más corto a cada punto de destino ahorrando tiempo de viaje y combustible.
2. Prim quiere saber cómo implementar de manera eficiente un sistema ferroviario, es decir, ahorrando costos de material.

Directamente del artículo de wikipedia del algoritmo de Dijkstra :

El proceso que subyace al algoritmo de Dijkstra es similar al proceso codicioso utilizado en el algoritmo de Prim. El propósito de Prim es encontrar un árbol de expansión mínimo que conecte todos los nodos del gráfico; Dijkstra se ocupa únicamente de dos nodos. Prim's no evalúa el peso total de la ruta desde el nodo inicial, solo la ruta individual.

Últimamente me molestaba la misma pregunta y creo que podría compartir mi comprensión ...

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). La formal es encontrar el camino más corto entre decir, el nodo s y t , y un requisito racional es visitar cada borde de la gráfica como máximo una vez. Sin embargo, NO nos obliga a visitar todo el nodo. El último (MST) es hacernos visitar TODO el nodo (como máximo una vez), y con el mismo requisito racional de visitar cada borde como máximo una vez también.

Una vez dicho esto, Dijkstra nos permite "tomar atajo", siempre que puedo conseguir de s a t , sin preocuparse de las consecuencias - una vez que llegue a t , he terminado! Aunque también hay un camino desde s a t en el MST, pero esto s - t trayectoria se crea con consideraciones de todos los nodos de descanso, por lo tanto, este camino puede ser más largo que las s - t camino encontrados por el algoritmo de la 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á que tomemos el camino de abajo, ya que no nos importa el nodo del medio. Por otro lado, Prim nos devolverá un MST con los 2 bordes superiores, descartando el borde inferior.

Tal diferencia también se refleja en la sutil diferencia en las implementaciones: en el algoritmo de Dijkstra, uno necesita tener un paso de contabilidad (para cada nodo) para actualizar la ruta más corta de s , después de absorber un nuevo nodo, mientras que en el algoritmo de Prim, hay no hay tal necesidad.

La diferencia clave entre los algoritmos básicos radica en sus diferentes criterios de selección de bordes. Generalmente, ambos usan una cola de prioridad para seleccionar los siguientes nodos, pero tienen diferentes criterios para seleccionar los nodos adyacentes de los nodos de procesamiento actuales: el algoritmo de Prim requiere que los siguientes nodos adyacentes también se mantengan en la cola, mientras que el algoritmo de Dijkstra no:

def dijkstra(g, s):
    q <- make_priority_queue(VERTEX.distance)
    for each vertex v in g.vertex:
        v.distance <- infinite
        v.predecessor ~> nil
        q.add(v)
    s.distance <- 0
    while not q.is_empty:
        u <- q.extract_min()
        for each adjacent vertex v of u:
            ...

def prim(g, s):
    q <- make_priority_queue(VERTEX.distance)
    for each vertex v in g.vertex:
        v.distance <- infinite
        v.predecessor ~> nil
        q.add(v)
    s.distance <- 0
    while not q.is_empty:
        u <- q.extract_min()
        for each adjacent vertex v of u:
            if v in q and weight(u, v) < v.distance:// <-------selection--------
            ...

Los cálculos de vertex.distance son el segundo punto diferente.

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 un concepto de programación llamado 'algoritmo codicioso'

Si marca esta noción, visite

1. Nota de conferencia sobre algoritmo codicioso: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-greedy.pdf
2. Árbol de expansión mínimo: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/20-mst.pdf
3. Ruta más corta de una sola fuente: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/21-sssp.pdf

Algoritmo de Dijkstras se usa solo para encontrar el camino más corto.

En el árbol de expansión mínima (algoritmo de Prim o Kruskal) obtiene egdes mínimos con un valor de borde mínimo.

Por ejemplo: - Considere una situación en la que no desea crear una red enorme para la que necesitará una gran cantidad de cables, por lo que este recuento de cables se puede realizar utilizando el árbol de expansión mínimo (algoritmo de Prim o Kruskal) (es decir, lo hará darle un número mínimo de cables para crear una gran conexión de red con un costo mínimo).

Mientras que el "algoritmo de Dijkstras" se utilizará para obtener la ruta más corta entre dos nodos al conectar los nodos entre sí.

La explicación más simple es que en Prims no especificas el Nodo de inicio , pero en dijsktra (Necesitas tener un nodo de inicio) tienes que encontrar la ruta más corta desde el nodo dado a todos los demás nodos.

@templatetypedef ha cubierto la diferencia entre MST y la ruta más corta. Cubrí la diferencia del algoritmo en otro Entonces, responda demostrando que ambos se pueden implementar usando el mismo algoritmo genérico que toma un parámetro más como entrada: función f(u,v). La diferencia entre el algoritmo de Prim y Dijkstra es simplemente cuál f(u,v)usa.

A nivel de código, la otra diferencia es la API.

Inicializa Prim con un vértice de origen, s , es decir Prim.new(s),; s puede ser cualquier vértice, e independientemente de s , el resultado final, que son los bordes del árbol de expansión mínimo (MST), es el mismo. Para obtener los bordes MST, llamamos al métodoedges() .

Inicializa Dijkstra con un vértice de origen, s , es decir, Dijkstra.new(s)que desea obtener la ruta / distancia más corta a todos los demás vértices. Los resultados finales, que son la ruta / distancia más corta desde sa todos los demás vértices; son diferentes dependiendo de la s . Para obtener los caminos / distancias más cortos desde s hasta cualquier vértice, v , llamamos a los métodos distanceTo(v)y pathTo(v)respectivamente.