MAPA CONCEPTUAL ALGORITMOS

ALGORITMO DIJKSTRA

• Algoritmo utilizado para encontrar el camino más corto desde un nodo de origen hasta todos los demás nodos en un gráfico con pesos no negativos.

• Sistemas de navegación GPS

DEFINICIÓN

APLICACIONES

• Redes de telecomuni caciones.

• Por lo cual, se basa en un enfoque de búsqueda voraz (codicioso).

• Diseño de redes de transporte y logística...

ALGORITMO DIJKSTRA

• Encuentra rutas óptimas en gráficos dirigidos y no dirigidos.

• No se maneja gráficos con pesos negativos.

VENTAJAS

DESVENTAJAS

• Es eficiente para gráficos con un número moderado de aristas.

• Puede ser ineficiente en gráficos muy densos o muy grandes.

• Implementación sencilla.

ALGORITMO FLOYD-WARSHALL

• Análisis de redes sociales (encontrar caminos cortos entre personas).

• Algoritmo dinámico para lograr encontrar el camino más corto entre todos los pares de nodos en un gráfico, incluso con pesos negativos, siempre que no haya ciclos negativos.

DEFINICIÓN

APLICACIONES

• Simulación de tráfico de redes.

• Análisis de redes computacionales y flujos de datos.

FLOYD WARSHALL

• Maneja gráficos con pesos negativos

• Complejidad computacional O (V^3), lo que puede ser costoso para gráficos grandes.

DESVENTAJAS

VENTAJAS

• Encuentra soluciones para todos los pares de nodos simultáneamente.

• Consume más memoria en comparación con otros algoritmos.

• Implemenctación compacta.

DATOS GENERALES

Alumna: Bermúdez López Yasmin JohannaMatrícula: ES241110504Actividad 1, Árboles y su ClasificaciónAsignatura: Matemáticas DiscretasDocente: Karina Mejía PrietoGrupo: TM-KMDI-2402_B2-002

REFERENCIAS

• Universidad Abierta y a Distancia de México . (Ciudad de México, octubre del 2024). Unidad 3: Discretización Contenido nuclear. Programa de la unidad didáctica: Matemáticas discretas. https://dmd.unadmexico.mx/contenidos/DCEIT/Compartidas/MDI/U3/descargables/MDI_U3_Contenido.pdf• Rodríguez P. L.,. (2024). Algoritmo de Dijkstra & Floyd. lizardorodriguez.wordpress.cominvestigaciòn, análisis y diseño de algoritmos. https://lizardorodriguez.wordpress.com/unidad-3/algoritmo-de-dijkstra-floyd/• Mendoza I. & Ruedas L.. (Jan 31, 2021). Análisis de algoritmos. Análisis de algoritmos. https://medium.com/algoritmo-floyd-warshall/algoritmo-de-floyd-warshall-e1fd1a900d8• juanpi. (29 de diciembre de 2022). El algoritmo de Dijkstra. Kodifico. https://kodifi.co/el-algoritmo-de-dijkstra/• Muñoz M. S. A.. (19 jun 2013). Dijkstra. SlideShare. https://es.slideshare.net/slideshow/dijkstra-23199102/23199102#6

Ejemplo

Encaminamiento de paquetes por los routers, considerando una red telefónica, en un momento dado, un mensaje puede tardar una cierta cantidad de tiempo en atravesar cada línea. En este caso se tiene una red con costes en los arcos y 2 nodos especiales, el nodo de comienzo y el de finalización. El objetivo aquí es, encontrar un camino entre dos nodos cuyo coste total sea el mínimo.

Recomendaciones

A través del uso de las matrices resultantes, se puede saber no solo la distancia mínima entre el punto de salida y el de llegada, sino también la ruta a utilizar. Esto podrá ahorrar tiempo y dinero en cada entrega, a la vez de maximizar el número de pedidos que pueden recibirse, por lo que considerar este plan de acción resultaría beneficioso para el negocio en todos los aspectos.

Análisis del algoritmo

Al momento de analizar un algoritmo revisamos el conjunto de operaciones primitivas de alto nivel que son independientes del lenguaje de programación que se utilice, estas pueden ser identificadas en el pseudocódigo del mismo.

Concepto

También llamado algoritmo de caminos mínimos es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959. La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene.

Dijkstra

Concepto

El algoritmo de Floyd-Warshall es un algoritmo de análisis de gráficas para que, de forma eficiente y simultánea, encuentre los caminos más cortos dentro de una gráfica en la cual las aristas tengan un costo (distancia entre nodo y nodo, duración del viaje entre nodos, etc.). Al ejecutar el algoritmo encontrara el camino menor o más corto de entre todos los pares de vértices, pero no devuelve los detalles de los caminos en sí. El algoritmo es un ejemplo de la Programación Dinámica y su variación más conocida fue publicada en 1962 por Robert Floyd.

Floyd-Warshall

Algoritmo de Floyd-Warshall

El algoritmo de Floyd-Warshall no permite la existencia de ciclos con peso negativo, ya que en ese caso no sería capaz de encontrar la distancia mínima entre cada par de vértices. Sin embargo, esto no supone un problema, puesto que el algoritmo es capaz de detectar la existencia de dichos ciclos.

Ventajas

Teorema

Es muy popular en los mapas geográficos . Se utiliza para localizar los puntos del mapa que corresponden a los vértices del gráfico. Para identificar el Open Shortest Path First, se necesita en el enrutamiento IP. La red telefónica hace uso de él.

El algoritmo de Dijkstra realiza =(n^2) operaciones (sumas y comparaciones) para determinar la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido con n vértices..

Desventajas

Sin embargo, el algoritmo de Dijkstra tiene una complejidad de O(nlogn), lo que significa que no es adecuado para grafos muy grandes. Existen algunas variantes del algoritmo, como el algoritmo de Bellman-Ford, que son más adecuados para grafos muy grandes pero tienen una complejidad más alta.

Reconocimiento de lenguaje hablado

Complejidad

Tiene un orden de complejidad este algoritmo O(/V/^2+/E/==(/V/^2) sin utilizar cola de prioridad, O((/E/+/V/) log/V/) utilizando cola de prioridad (por ejemplo un montículo).

Un problema que se presenta es el distinguir entre palabras que suenan de manera similar. Se puede construir un grafo cuyos vértices correspondan a palabras posibles y cuyos arcos unan palabras que puedan ir colocadas una al lado de otra.