algorithm - geeksforgeeks - ¿Diferencia entre los algoritmos de Prim y Dijkstra?

prim''s algorithm geeksforgeeks

Question

¿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?

Answer 1

Dijkstra encuentra la ruta más corta entre su nodo inicial y cada otro nodo. Entonces, a cambio, obtiene el árbol de distancia mínima desde el nodo inicial, es decir, puede llegar a todos los demás nodos 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 el mínimo posible.

Para resumir una historia con un ejemplo realista:

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

Answer 2

@templatetypedef ha cubierto la diferencia entre MST y el camino más corto. He cubierto la diferencia del algoritmo en otra respuesta de So al demostrar que ambas pueden implementarse utilizando el mismo algoritmo genérico que toma un parámetro más como entrada: función f(u,v) . La diferencia entre Prim y el algoritmo de Dijkstra es simplemente qué f(u,v) usas.

Answer 3

Directamente del artículo de wikipedia del Dijkstra''s Algorithm :

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 en el gráfico; Dijkstra solo se preocupa por dos nodos. Prim no evalúa el peso total de la ruta desde el nodo inicial, solo la ruta individual.

Answer 4

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

Considera este gráfico

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

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

Answer 5

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 en el 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 cualquiera 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 sea óptima, ya que lo único que te importa es el hecho de que están conectados.

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

Otra diferencia importante se refiere a qué tipos de gráficos trabajan los algoritmos. El algoritmo de Prim solo funciona en gráficos no dirigidos, ya que el concepto de un MST supone que los gráficos son inherentemente no dirigidos. (Hay algo llamado "arborescencia de extensió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 los árboles de ruta más cortos pueden ser dirigidos. Además, el algoritmo de Dijkstra no arroja necesariamente la solución correcta en gráficos que contienen pesos de borde negativo , mientras que el algoritmo de Prim puede manejar esto.

¡Espero que esto ayude!

Answer 6

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

Inicializas Prim con un vértice fuente, 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), son los mismos. Para obtener los bordes MST, llamamos al método edges() .

Inicializas Dijkstra con un vértice fuente, s , es decir, Dijkstra.new(s) que quieres 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 s a todos los demás vértices; son diferentes dependiendo del s . Para obtener las trayectorias / distancias más cortas de s a cualquier vértice, v , llamamos a los métodos distanceTo(v) y pathTo(v) respectivamente.

Answer 7

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.

Answer 8

La primera distinción es que el algoritmo de Dijkstra resuelve un problema diferente al de Kruskal y Prim. Dijkstra resuelve el problema de ruta más corta (desde un nodo especificado), 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 de 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 menor peso total 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.

Para un vértice específico (por ejemplo, X), el árbol de ruta más corto es un árbol de expansión de manera que la ruta desde X a cualquier otro vértice sea lo más corta posible (es decir, tenga 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 económica que satisfaga nuestras necesidades. Mientras tanto, Kruskal es un algoritmo "global", lo que significa que cada borde se elige (codiciosamente) de todo el gráfico. (En realidad, se puede considerar 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 disponible más barato 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 el borde disponible más barato adjunto a cualquier vértice previamente elegido que no viole el objetivo de crear un árbol de expansión. Para encontrar un árbol de expansión de ruta más corta:

Dijkstra: en cada paso, elija el borde asociado a cualquier vértice elegido anteriormente (el aspecto local) que hace que la distancia total desde el vértice de inicio (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 se elige un borde que conecta un vértice Y que está en el árbol con un vértice Z que no lo es. 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 siguiente gráfico, empezando por 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 borde DC, mientras que Dijkstra agrega AC o BC, porque los caminos AC y ABC (ambos con una distancia total 30) son más cortos que el camino ABDC (distancia total 31).

Answer 9

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

En Prim:

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) and w(u,v) < v.key

                    v.parent = u
                    v.key = w(u,v)    <== relax function, Pay attention here

}

En 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) and w(u,v) < v.key

                    v.parent = u
                    v.key = w(u,v) + u.key  <== relax function, Pay attention here

}

La única diferencia es la última línea del código, 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. por lo que se ve así: v.key = w (u, v) Dijkstra, que busca la longitud de ruta mínima, por lo que le importa la acumulación de bordes. Entonces parece: v.key = w (u, v) + u.key

Answer 10

El 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 de Kruskal) se obtienen mínimos egdes con un valor de borde mínimo.

Por ejemplo: - Considere una situación en la que desee crear una gran red para la cual necesitará una gran cantidad de cables, de modo que el conteo de cables se puede hacer usando el árbol de expansión mínimo (algoritmo de Prim o de Kruskal) (es decir, darle la cantidad mínima de cables para crear una gran conexión de red por cable con un costo mínimo).

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