S3.8- Algoritmo de Floyd-Warshall (2) | 35/49 | UPV

Title: S3.8- Floyd-Warshall Algorithm (2) Self-description: In this video, we continue the analysis of Floyd's algorithm, focusing on how to determine the specific vertices that comprise the shortest path between two points in a graph, as the calculation of weights was discussed in a previous video. A motivating example is presented using pre-calculated values illustrating the costs of traveling from one point to another in a city. To this end, we explain the use of a vertex matrix where each element indicates the previous vertex on the shortest path between two points. This matrix allows the path to be reconstructed by working backward from the destination to the origin. A generic example shows how to update the vertex matrix when a shorter path is found through an intermediate vertex. The process involves updating the vertex matrix with the correct previous vertices as the shortest paths found change. In the end, a matrix is obtained that allows you to reconstruct any shortest path between two vertices by following the previous vertices from the destination to the origin. The video promises to continue with a complete example in the next installment, where the weights and the construction of the vertex matrix will be covered simultaneously, further clarifying how Floyd's algorithm works. Author: Jordan Lluch Cristina Course: This video is 35/49 of the MOOC course Applications of Graph Theory to Real Life I | Universitat Politècnica de València UPV.    • MOOC Aplicaciones de la Teoría de Grafos a...   Polytechnic University of Valencia (UPV): https://www.upv.es More videos at:    / valenciaupv   Access our MOOCs: https://upvx.es #theory #graphs #mathematics #graphs #weighted #algorithm #floyd-warshall #mathematics