5.2 Algoritmo de Floyd-Warshall

El algoritmo de Floyd-Warshall es la opción utilizada cuando se desea determinar el camino mínimo entre todos los pares de vértices de un grafo, comparando todos los posibles caminos logra mejorar paulatinamente la estimación hasta llegar a la más óptima.

Para entender un poco mas su funcionamiento adjunto el funcionamiento de este algoritmo ( de la pagina científica Learn tutorial)

Lo primero que hacemos es tomar dos matrices 2D. Estas son matrices de adyacencia . El tamaño de las matrices será el número total de vértices. Para nuestra gráfica, tomaremos 4 * 4 matrices. La Matriz de distancia almacenará la distancia mínima encontrada hasta ahora entre dos vértices. Al principio, para los bordes, si hay un borde entre uv y la distancia / peso es w , almacenaremos: distance[u][v] = w . Por todos los bordes que no existen, vamos a poner el infinito . La Matriz de ruta es para regenerar la ruta de distancia mínima entre dos vértices. Entonces, inicialmente, si hay una ruta entre u y v , vamos a poner la path[u][v] = u . Esto significa que la mejor manera de llegar al vértice-v del vértice-u es usar el borde que conecta v con u. Si no hay una ruta entre dos vértices, vamos a poner N allí para indicar que no hay una ruta disponible ahora. Las dos tablas para nuestra gráfica se verán como: