Act 2 - Algoritmos de Kruskal, Prim y Dijkstra

<Algoritmo de Kruskal, Prim y Dijkstra>

Comparación y Propósitos>

<Equipo>

• Freda Maria Perez Novelo
• Brisa Jael Lima Arenas
• Marco Emiliano Santamaria Vargas
• Karina Jaqueline Cosgaya Lupercio

EMPEZAR >

<14 de Octubre 2024>

>

>

<Introducción>

Árboles de expansión mínima (MST): En teoría de grafos, un árbol de expansión mínima conecta todos los vértices de un grafo ponderado con el costo total más bajo posible y sin formar ciclos.

Búsqueda de caminos más cortos: Se enfoca en identificar la ruta con el menor peso o costo entre dos nodos específicos en un grafo ponderado. Es fundamental en áreas como la planificación de rutas de navegación, la optimización de redes logísticas, y los sistemas de navegación GPS.

Los algoritmos de Kruskal, Prim y Dijkstra se utilizan para resolver dos problemas clave en grafos ponderados: la construcción de árboles de expansión mínima (Kruskal y Prim) y la búsqueda de caminos más cortos (Dijkstra).

>

<Kruskal>

>

El algoritmo de Kruskal sirve para encontrar el árbol de expansión mínima en un grafo, conectando todos los vértices con el menor costo posible y sin formar ciclos.

¿Que pasos sigue?

1. Ordenar los bordes por peso. 2. Inicializar el árbol vacío y los conjuntos disjuntos. 3. Añadir bordes evitando ciclos hasta alcanzar V−1V−1 bordes.

<Proposito de kruskal>

>

>

El propósito del algoritmo de Kruskal es encontrar el árbol de expansión mínima (Minimum Spanning Tree, MST) en un grafo no dirigido y ponderado. Un árbol de expansión mínima es un subconjunto de los bordes del grafo que conecta todos los vértices con el costo total mínimo y sin formar ciclos. El algoritmo está diseñado para: 1.Minimizar el costo total de conectar todos los vértices. 2.Evitar la formación de ciclos en el proceso de conexión. 3.Ser eficiente en grafos con muchos bordes (es decir, cuando los grafos son densos).

>

>

¿Como funciona el algoritmo de Prim?

1. Inicializar desde un vértice arbitrario. 2. Añadir bordes de menor peso que conectan el árbol con vértices externos. 3. Repetir hasta incluir todos los vértices.

>

>

// Cual es el proposito del algoritmo pRIM

El propósito del algoritmo de Prim es encontrar el árbol de expansión mínima en un grafo no dirigido y ponderado. Específicamente, su objetivo es: Conectar todos los vértices: Asegurarse de que todos los vértices del grafo estén conectados entre sí. Minimizar el costo total: Seleccionar los bordes de menor peso para minimizar el costo total de la conexión. Evitar ciclos: Construir el árbol de expansión mínima sin formar ciclos entre los vértices.

>

>

// Algoritmo de dijkstra

Es un algoritmo que encuentra el camino más corto desde un vértice inicial a todos los demás vértices en un grafo ponderado con pesos no negativos. Al aplicarlo, el algoritmo encuentra la distancia mínima de cada vértice desde el vértice inicial, lo que genera una lista o mapa de distancias mínimas a cada vértice del grafo.

1. Inicializar todas las distancias a infinito, excepto la del vértice inicial, que se establece en 0.
2. Marcar el vértice inicial como visitado.
3. Para cada vértice no visitado adyacente, calcular la distancia desde el vértice actual. Si esta distancia es menor que la distancia previamente registrada, actualizarla.
4. Marcar el vértice actual como visitado.
5. Repetir el proceso desde el vértice con la menor distancia registrada hasta que todos los vértices hayan sido visitados.

>

>

// Propósito del Algoritmo de Dijkstra

Este algoritmo es fundamental en aplicaciones donde se necesita la ruta más rápida o eficiente, como en sistemas de navegación, redes de comunicación y optimización de rutas en logística.

https://onlinegdb.com/ihoeJmHHj

>

<Diferencias entre Algoritmos>

>

Estructura del Grafo

Estrategia

Método de Selección

Complejidad Computacional

Método de Selección

Kruskal

Prim

Dijkstra

>

>

<Conclusión>

Los algoritmos de Kruskal, Prim y Dijkstra son pilares en la teoría de grafos y la optimización. La elección del algoritmo adecuado depende significativamente de la estructura del grafo y el tipo de problema que se desee resolver. Grafos dispersos son más aptos para Kruskal, mientras que Prim es preferible en grafos densos. Por otro lado, Dijkstra es la opción adecuada para problemas de rutas donde los pesos son no negativos.

Ambos algoritmos se especializan en la construcción de árboles de expansión mínima (MST), aunque abordan el problema desde diferentes perspectivas. Kruskal se enfoca en la selección de aristas de menor peso de manera global, mientras que Prim expande un árbol a partir de un único vértice, incorporando aristas de menor costo de manera local.

Dijkstra está diseñado para encontrar el camino más corto desde un vértice inicial a todos los demás en un grafo.

>

>

// Zona de preguntas

//Gracias!!

>

>

+ info

< Volver

EMPEZAR >

00