Árbol de expansión mínimo vs ruta más corta

¿Cuál es la diferencia entre el algoritmo de árbol de expansión mínimo y un algoritmo de ruta más corta?

En mi clase de estructuras de datos cubrimos dos algoritmos de árbol de expansión mínimo (Prim y Kruskal) y un algoritmo de ruta más corta (Dijkstra).

El árbol de expansión mínimo es un árbol en un gráfico que abarca todos los vértices y el peso total de un árbol es mínimo. La ruta más corta es bastante obvia, es una ruta más corta de un vértice a otro.

Lo que no entiendo es que, dado que el árbol de expansión mínima tiene un peso total mínimo, ¿no serían los caminos en el árbol los más cortos? ¿Alguien puede explicar lo que me falta?

Cualquier ayuda es apreciada.

$x,y,z$$\{x,y\},\{x,z\},\{y,z\}$$1$$\{x,y\},\{y,z\}$$\{x,z\}$

En conclusión, si juntas todos los caminos más cortos, no necesariamente obtienes un árbol.

Tiene razón en que los dos algoritmos de Dijkstra (rutas más cortas desde un solo nodo de inicio) y Prim (árbol de expansión de peso mínimo a partir de un nodo dado) tienen una estructura muy similar. Ambos son codiciosos (toman la mejor ventaja desde el punto de vista actual) y construyen un árbol que abarca el gráfico.

Sin embargo, el valor que minimizan es diferente. Dijkstra selecciona como siguiente borde el que sale del árbol a un nodo que aún no se ha elegido más cerca del nodo inicial. (Luego, con esta elección, las distancias se vuelven a calcular.) Prim elige como borde el más corto que sale del árbol construido hasta ahora. Entonces, ambos algoritmos eligieron una "ventaja mínima". La principal diferencia es el valor elegido para ser mínimo. Para Dijkstra, es la longitud de la ruta completa desde el nodo de inicio hasta el nodo candidato, para Prim es solo el peso de ese borde único.

$x,y,z$$\{x,y\}$$\{x,z\}$$\{y,z\}$$x$$\{x,y\}$$\{x,z\}$$\{x,y\}$$\{y,z\}$

En cuanto a Kruskal , eso es un poco diferente. Resuelve el árbol de expansión mínimo, pero durante la ejecución elige el borde que puede no formar un árbol, solo evitan los ciclos. Entonces las soluciones parciales pueden ser desconectadas. Al final obtienes un árbol.

Aunque el cálculo de algoritmos de árbol de expansión mínimo y ruta más corta es similar, se centran en 2 requisitos diferentes.

En MST, el requisito es alcanzar cada vértice una vez (crear árbol de gráficos) y el costo total (colectivo) de alcanzar cada vértice debe ser mínimo entre todas las combinaciones posibles.

En la ruta más corta, el requisito es alcanzar el vértice de destino desde el vértice de origen con el menor costo posible (menor peso). Entonces, aquí no nos preocupamos por alcanzar cada vértice, sino que solo nos enfocamos en los vértices de origen y destino, y ahí es donde radica la diferencia.

Aquí está el ejemplo para aclarar por qué MST no necesariamente da la ruta más corta entre 2 vértices.

(A)----5---(B)----5---(C)
 |                     |
 |----------7----------| 

En el caso de MST, bordes AB. BC estará en MST con un peso total de 10. Por lo tanto, el costo de llegar de A a C en MST es 10.

Pero en el caso de la ruta más corta, la ruta más corta entre A y C es AC, que es 7. AC nunca estuvo en MST.

La diferencia radica en cuál es el objetivo final de este algoritmo:

Dijkstra's - Aquí el objetivo es llegar de principio a fin. Solo le preocupan estos 2 puntos y optimice su camino en consecuencia.

Krusal's: aquí puede comenzar desde cualquier punto y visitar todos los demás puntos del gráfico. Por lo tanto, no siempre puede elegir el camino más corto para cualquiera de los dos puntos. En cambio, el enfoque es elegir el camino que lo llevará a un camino más corto para todos los demás puntos.

Creo que un ejemplo lo aclarará.

El árbol de expansión se ve a continuación. Esto se debe a que si sumamos los bordes en esta configuración, obtenemos el menor costo total posible : 2 + 5 + 14 + 4 = 25.

(1)   (4)
  \   /
   (2)
  /   \
(3)   (5)

Al observar el árbol de expansión, puede pensar falsamente que le brinda los caminos más cortos, pero en la práctica no lo hace. Como ejemplo, si quisiéramos pasar de un nodo (1)a otro (4)nos costaría 7. Sin embargo, si utilizáramos el algoritmo de Dijkstra en el gráfico original, encontraríamos que podemos ir directamente de un nodo (1)a (4)un costo de 5.

Ejemplo práctico para mostrar la diferencia>

Suponga que llega en tren a una ciudad y quiere llegar a su hotel.

Opción 1: tome un taxi: el taxi tomará el camino más corto hasta su hotel desde la estación. Si el conductor debe seguir un camino a lo largo del árbol de ruta más corto centrado en la estación.

Opción 2: tomar un autobús. La compañía de autobuses quiere atender a muchas personas, no solo a usted. El camino ideal abarcaría todos los puntos clave de la ciudad. Entonces seguirá (*) un camino a lo largo del árbol de expansión mínimo. Es por eso que el autobús es más lento, pero a medida que se comparten los costos, es más barato.

(*) En realidad, las personas se quejarían si se utilizara el árbol de expansión mínimo (el viaje en autobús sería demasiado largo). Por lo tanto, en la práctica sería una solución mixta y utilizaría un árbol alfa (a medio camino entre un árbol de expansión mínima y un árbol de ruta más corta).

Se basan en dos propiedades diferentes. El árbol de expansión mínimo se basa en la propiedad de corte, mientras que la ruta más corta se basa en la propiedad de relajación del borde.

Un corte divide un gráfico en dos componentes. Puede involucrar múltiples bordes. En MST, seleccionamos el borde con el menor peso.

La relajación de bordes dice que dado que conozco la distancia entre A y B: dist (a, b) y dist entre A y C: dist (a, c), si dist (a, b) + edge (b, c) es menor que dist (a, c), entonces puedo relajar edge (ac). Después de relajar todos los bordes, obtenemos el camino más corto.

Recomiendo ver el video sobre algoritmos gráficos del profesor Robert Sedgewick.