El algoritmo de Floyd-Warshall, explicado en 1959 por
Bernard Roy, es un algoritmo de análisis de grafos para encontrar el camino
mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre
todos los pares de vértices en una única ejecución.
Trabaja con la matriz D inicializada con las distancias
directas entre todo par de nodos. La iteración se realiza sobre nodos
intermedios, es decir, para todo elemento de la matriz se prueba si lo mejor
para ir de i a j es a través de un nodo intermedio elegido o como estaba antes,
y esto lo probamos con todos los nodos de la red. Una vez probados todos los
nodos de la red como nodos intermedios, la matriz resultante da la mejor
distancia entre todo par de nodos.
No hay comentarios:
Publicar un comentario