ESTADO DEL ARTE

El algoritmo de Floyd es muy similar al Warshall, pero trabaja con grafos ponderados. Es decir, el valor de la “flecha” que representamos en la matriz puede ser cualquier entero que se nos ocurra, o infinito. Infinito marca que no existe unión entre los nodos. Esta vez, el resultado será una matriz donde estarán representadas las distancias mínimas entre nodos, seleccionando los caminos más convenientes según su ponderación (“peso”). Por ejemplo, si de “A” a “B” hay 36 (km), pero de “A” a “C” hay 2(km) y de “C” a “B” hay 10 (km), el algoritmo nos devolverá finalmente que de “A” a “C” hay 12 (km).

El algoritmo de Warshall es un ejemplo de algoritmo booleano. A partir de una tabla inicial compuesta de 0`s (no hay correspondencia inicial en el grafo) y 1`s (hay una correspondencia, llamase “flecha”, entre nodos), obtiene una nueva matriz denominada “Matriz de Clausura Transitiva” en la que se muestran todas las posibles uniones entre nodos, directa o indirectamente. Es decir, si de “A” a “B” no hay una “flecha”, es posible que si haya de “A” a “C” y luego de “C” a “B”. Luego, este resultado se verá volcado en la matriz final.

El algoritmo de Floyd-Warshall es un algoritmo de análisis de grafos para que, de forma eficiente y simultánea, encuentre los caminos más cortos dentro de un grafo en el cual las aristas tengan un costo (distancia entre nodo y nodo, duración del viaje entre nodos, etc.). Al ejecutar el algoritmo encontrara el camino menor o más corto de entre todos los pares de vértices, pero no devuelve los detalles de los caminos en sí. El algoritmo es un ejemplo de la Programación Dinámica y su variación más conocida fue publicada en 1962 por Robert Floyd. Aunque es necesario comentar también que es esencialmente el mismo algoritmo descubierto independientemente y antes publicado por Bernard Roy en 1959 y por Stephen Warshall en 1962. De ahí sus múltiples pseudónimos: Algoritmo de Floyd, Algoritmo de Roy-Floyd, Algoritmo de Roy-Warshall, Algoritmo WFI.