S3.6- Algoritmo de Floyd-Warshall | 34/49 | UPV
ฝัง
- เผยแพร่เมื่อ 19 ก.ย. 2024
- Título: S3.6- Algoritmo de Floyd-Warshall
Descripción automática: En este video se inicia el análisis del algoritmo de Floyd-Warshall, aplicado en el contexto de problemas de caminos más cortos. Se explica que, a diferencia de Dijkstra, que busca el camino más corto entre un punto y todos los otros, Floyd-Warshall se enfoca en encontrar la mínima distancia entre todos los pares de puntos.
Se presenta el escenario de Sergio, quien desea optimizar su ruta en coche entre varios puntos de la ciudad. Su objetivo es obtener una tabla que refleje el camino más corto entre cada par de puntos y, si existen rutas indirectas más baratas, conocer los vértices que conforman esos trayectos.
Para ello, se plantea el uso de matrices donde se reflejarán los costes y los vértices que componen el camino más corto para cada pareja de puntos. Se hace hincapié en tener precaución con los valores negativos que pueden aparecer en las ponderaciones y cómo estos pueden representar, por ejemplo, beneficios en lugar de costes.
Durante la exposición, se clarifica que los ciclos de peso negativo en los grafos pueden conducir a resultados sin solución, ya que permitirían disminuir el coste indefinidamente, creando un bucle infinito. Por tanto, cualquier ciclo de peso negativo debe ser solucionado antes de aplicar el algoritmo.
Finalmente, se describe la idea central del algoritmo: comparar el coste de un camino directo entre dos puntos con el coste de caminos que pasan por un vértice intermedio, buscando reducir el coste total del trayecto. El método se basa en la actualización progresiva de los costes a medida que se evalúan distintos vértices intermediarios.
El video concluye anticipando que estas ideas y el algoritmo en sí se detallarán y clarificarán en un próximo video con ejemplos prácticos.
Autor/a: Jordan Lluch Cristina
Curso: Este vídeo es el 34/49 del curso MOOC Aplicaciones de la Teoría de Grafos a la vida real I | Universitat Politècnica de València UPV. • MOOC Aplicaciones de l...
+ Universitat Politècnica de València UPV: www.upv.es
+ Más vídeos en: / valenciaupv
+ Accede a nuestros MOOC: upvx.es
#teoría #grafos #matemáticas #grafos #ponderados #algoritmo #floyd-warshall #matemáticas
Felicidades profesora Jorda Lluch su presentación me ha sido de gran ayuda y su estilo me parece sumamente claro y fluido
Hola, ¡gracias! Me alegro de que te haya sido útil.
Si quieres ver más vídeos de grafos o matemática discreta en general puedes consultar mi canal "el lado discreto de las mates" a ver si te valen, 😉cada año añado unos cuántos vídeos.
Saludos
Cristina
Muchas Gracias por la explicación y dedicarle tiempo a la enseñanza libre y autodidacta :D
Saludos
Excelente video. Muchas gracias.
Muy bueno!!
Que programa usan para construir los vídeos?
El vídeo se ha grabado es un estudio denominado Polimedia con un software específico que hemos creado en la UPV. Para conseguir un efecto similar puedes usar Open Broadcaster Software obsproject.com/es/download
Gracias, Excelente trabajo!
en Colombia los vemos
www.lacoloniafilms.com
@lacoloniafilms