Act 2 - Algoritmos de Kruskal, Prim y Dijkstra

Algoritmos de Kruskal, Prim y Dijkstra

Comparación y Propósitos

Integrantes

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

14 de octubre de 2024

INTRODUCCIÓN

Á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.

Algoritmo de Kruskal

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 (Proposito)

• 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 Prim

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 (Propósito)

• 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.

Ejemplo

Algoritmo de Dijkstra

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 (Propósito)

• 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.

Ejemplo

Diferencia entre Kruskal, Prim y Dijkstra

Complejidad computacional

• 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.

Estrategia

Estructura de grafo

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

Método de selección

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

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

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

Conclusiones

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.

Preguntas y Respuestas

Bibliografia

• 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)