La diferencia entre los algoritmos Prim y Dijkstra

En teoría de grafos, el algoritmo de Prim es un algoritmo para calcular el árbol de expansión mínimo y el algoritmo de Dijkstra es un algoritmo para calcular el camino más corto. Los dos se ven similares, porque suponiendo que el conjunto de todos los vértices es V y el conjunto de puntos seleccionados es U, ambos seleccionan continuamente los puntos con el peso más bajo del conjunto V-U para agregarlos a U.

La diferencia entre los dos es que la definición de "peso más bajo" es diferente. El "peso más bajo" de Prim es relativo a cualquier punto en U, es decir, considerando los puntos en U en su conjunto. cada vez que el punto en V-U con la distancia más pequeña desde U (es decir, la distancia más pequeña con cualquier punto en U) se encuentra y se suma a U y el "peso más bajo" de Dijkstra es relativo a v0, es decir, cada vez Encuentre el; punto en V-U con la distancia más pequeña desde v0 y súmalo a U.

Un ejemplo que ilustra la inequivalencia entre ambos es que hay cuatro vértices (v0, v1, v2, v3) y cuatro aristas, y los valores de las aristas se definen como (v0, v1)= 20, (v0, v2) = 10, (v1, v3) = 2, (v3, v2) = 15, v0 y v1 no están conectados directamente en el árbol de expansión mínimo obtenido por el algoritmo de Prim, es decir, v0v1 en el mínimo. árbol de expansión La distancia es v0-gt; v2-gt; v3-gt; la distancia de v1 es 27 y la distancia de v0v1 obtenida usando el algoritmo de Dijkstra es 20, que es la longitud de la conexión directa entre los dos.