Grafos: Camino mínimo con algoritmo de DIJKSTRA | | UPV

Título: Grafos: Camino mínimo con algoritmo de DIJKSTRA

Descripción: Resolución de problema ejemplo camino mínimo en un grafo mediante el algoritmo de Dijsktra Miralles Insa, CJ. (2021). Grafos: Camino mínimo con algoritmo de DIJKSTRA. Universitat Politècnica de València. http://hdl.handle.net/10251/167523

Descripción automática: En este video, se explica el problema del camino mínimo en grafos y el uso del algoritmo de Dijkstra para resolverlo. El objetivo es definir el problema y aplicar paso a paso el algoritmo en un ejemplo sencillo para interpretar la solución óptima y entender sus ventajas y limitaciones.

El problema del camino mínimo consiste en encontrar la distancia más corta entre un nodo inicial y cualquier otro nodo de un grafo. Utilizando un ejemplo, se muestra cómo comenzar con una tabla de distancias inicializada y cómo iterar para evaluar la distancia más corta. Se etiqueta para cada nodo la distancia total acumulada y se selecciona el nodo adyacente por el que se ha llegado.

El proceso se repite excluyendo nodos que ya han sido asignados al camino mínimo y evaluando los caminos disponibles desde el conjunto de nodos restantes. Esta evaluación recurrente lleva a la ruta óptima. Al final se ofrece la solución que representa el camino mínimo desde el punto inicial a todos los demás nodos.

El video termina resaltando que el algoritmo de Dijkstra es aplicable tanto a grafos orientados como no orientados y que su ventaja es la posibilidad de terminar la búsqueda una vez que se alcanza el vértice objetivo. No obstante, la limitación del algoritmo es que solo funciona para grafos con valores de distancia no negativos.

Autor/a: Miralles Insa Cristóbal Javier



Universitat Politècnica de València UPV: https://www.upv.es
Más vídeos en:    / valenciaupv  
Accede a nuestros MOOC: https://upvx.es

#Grafos #Camino mínimo #Algoritmo de DIJKSTRA #ORGANIZACION DE EMPRESAS #1207 - Investigación operativa