Problema del camino más corto Algoritmo Floyd Warshall Parte 1

En este vídeo resolvemos un ejercicio del camino más corto con el algoritmo Floyd-Warshall

[@luismatiasjavierpereiratol425]

en el minuto 13:40 hay un error, lo dejaste como 9 y deberia ser 6, buen video :)

[@jesuszepeda5503]

Gracias 😊

[@emanuellemos5818]

te hago una consultas. si yo quiero entregar varios paquetes (partiendo desde un punto ) que algoritmo seria el recomendado para eso ? imaginate un camion que sale un dia y tiene que entregar varios paquetes, que algoritmo le diria la mejor ruta ? (primero anda a este punto, despues al otro, despues al otro)

[@jesuszepeda5503]

Tendrías que verificar si tú grafo es euleriano, si lo es, significa que tendrás que pasar por todas los lugares (calles de entrega, sin repetir alguna) y te serviría esa ruta que es la óptima, sacando el ciclo euleriano. Sí no es euleriano tendrías que forzar a qué lo sea (repetir calles para regresar a algún lugar, por ejemplo). Las características de un grafo elueriano es que debe ser conexo y el grado de todos sus vértices debe ser par.

[@jesuszepeda5503]

Otra cosa, te sugiero grafos eulerianos porque vas a ser un recorrido de circuito cerrado, supongo que regresaras al finalizar la entrega al vértice de partida. No recomiendo el algoritmo Floyd-Warshal ni Dijkstra por qué son específicos para obtener un árbol, el cual no contiene ciclos (siempre, porque esa es una característica de éstos). Generalmente estos algoritmos son usados para hacer carreteras, vías férreas, cableado de circuitos o computadoras, ya que optimizan material o mano de obra y conectan a todos los lugares. Mientras que los grafos eulerianos(pasa por todos los artistas sin repetir alguno, aunque los vértices si) se usan más para recorridos como el que específicas. También los grafos hamiltonianos (se pasa por todos los vértices, sin repetir alguno) se usan para recorridos. Saludos cordiales.