Act 2 - Algoritmos de Kruskal, Prim y Dijkstra

Alecio Garcia Ricardo Barragan de la Cruz Ulises Benitez Rental Kenny Yaritza Ramon Perez Amariani Guadalupe

14 de octubre de 2024

Integrantes

Comparación y Propósitos

Algoritmos de Kruskal, Prim y Dijkstra

Árbol de expansión mínima (MST): Un árbol de expansión mínima es un subgrafo que conecta todos los vértices de un grafo ponderado sin formar ciclos y con el peso total mínimo posible. Es clave en aplicaciones como el diseño de rutas de Internet y redes eléctricas. Caminos más cortos: El algoritmo de Dijkstra busca el camino más corto entre un punto inicial y los demás en el grafo. Importancia de los algoritmos: Los algoritmos de Kruskal y Prim encuentran el árbol de expansión mínima, conectando todos los puntos con el menor costo, sin crear ciclos. Estos algoritmos son ampliamente utilizados en la optimización de redes y sistemas de transporte.

INTRODUCCIÓN

El algoritmo de Kruskal busca construir un Árbol de Expansión Mínima (MST) seleccionando los bordes más ligeros (con menor peso) de un grafo, asegurando que no se formen ciclos. Este proceso conecta todos los vértices del grafo con el costo total mínimo. Pasos:

• Ordenar todos los bordes del grafo por su peso (de menor a mayor).
• Inicializar un árbol vacío y crear conjuntos separados para cada vértice.
• Añadir los bordes, uno por uno, siempre que no formen un ciclo, hasta tener V−1 bordes (donde V es el número de vértices).

Algoritmo de Kruskal

• El objetivo del algoritmo de Kruskal es conectar todos los vértices con el costo total mínimo sin formar ciclos.

• Es útil cuando trabajas con grafos dispersos, es decir, aquellos con relativamente pocos bordes.

Algoritmo de Kruskal (Proposito)

El algoritmo de Prim construye el MST empezando desde un vértice inicial y expandiéndose gradualmente Pasos:

• Empezar desde un vértice arbitrario y marcarlo como parte del MST.
• Seleccionar el borde de menor peso que conecta un vértice en el MST con un vértice fuera del MST.
• Repetir el proceso hasta que todos los vértices estén en el MST.

Algoritmo de Prim

Ejemplo

• El objetivo de Prim es conectar todos los vértices de un grafo con el costo total mínimo, partiendo de un solo vértice.

• Este algoritmo es más eficiente para grafos densos, es decir, aquellos con muchos bordes.

Algoritmo de Prim (Propósito)

El algoritmo de Dijkstra encuentra el camino más corto desde un vértice inicial a todos los demás vértices en un grafo ponderado. Pasos:

• Inicializar las distancias de todos los vértices a infinito, excepto el vértice inicial, cuya distancia es 0.
• Marcar el vértice inicial como visitado.
• Para cada vértice no visitado, adyacente al vértice actual, calcular la distancia a través del vértice actual y actualizarla si es más corta.
• Marcar el vértice como visitado y repetir el proceso hasta que todos los vértices hayan sido visitados.

Algoritmo de Dijkstra

Ejemplo

• Dijkstra se utiliza para encontrar el camino más corto entre un vértice y todos los demás en un grafo ponderado.

• Es eficiente para aplicaciones donde se deben calcular rutas óptimas, como en sistemas de navegación o redes.

Algoritmo de Dijkstra (Propósito)

• Kruskal: O(E log E) Ordena los bordes y usa conjuntos disjuntos.
• Prim: O(E log V) Usa una cola de prioridad para seleccionar el borde más pequeño.
• Dijkstra: O(V²) o O(E + V log V) Depende si usa una cola de prioridad.

Complejidad computacional

• Kruskal: Divide y vencerás.
• Prim: Crecimiento desde un vértice.
• Dijkstra: Actualización de distancias.

Estrategia

• Kruskal: Funciona mejor en grafos dispersos.
• Prim: Funciona mejor en grafos densos.
• Dijkstra: Aplica en grafos ponderados con pesos no negativos.

Estructura de grafo

• Kruskal: Selección de bordes más ligeros.

• Prim: Expansión desde un vértice.
• Dijkstra: Selección de caminos más cortos.

Método de selección

Diferencia entre Kruskal, Prim y Dijkstra

Kruskal y Prim construyen árboles de expansión mínima, mientras que Dijkstra encuentra caminos más cortos. La elección del algoritmo depende de la estructura del grafo (disperso o denso) y del problema (MST o caminos más cortos). Tienen diferentes aplicaciones como por ejemplo, usar Kruskal en una red ferroviaria, Prim para cableado de una ciudad y Dijkstra para sistemas de navegación.

Conclusiones

Preguntas y Respuestas

• https://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_kruskal

• https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/

• https://runestone.academy/ns/books/published/pythoned/Graphs/AlgoritmoDePrimDelArbolDeExpansion.html

• https://www.freecodecamp.org/espanol/news/algoritmo-de-la-ruta-mas-corta-de-dijkstra-introduccion-grafica/

• https://youtu.be/OZKuWP1KxdY?si=QsZJ87E72VvhIaoZ (Algoritmo de Kruskal)

• https://youtu.be/EFg3u_E6eHU?si=JneP-I3qFv_Lmbkg (How Dijkstra's Algorithm Works)

Bibliografia