Es un algoritmo de análisis
sobre 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. El algoritmo de Floyd es un ejemplo de programación
dinámica.
El algoritmo de Floyd compara todos los posibles caminos a través del grafo entre cada par de
vértices. El algoritmo es capaz de hacer esto con sólo v3 comparaciones (esto
es notable considerando que puede haber hasta v2 aristas en el grafo, y que
cada combinación de aristas se prueba). Lo hace mejorando paulatinamente una
estimación del camino más corto entre dos vértices, hasta que se sabe que la
estimación es óptima.
Como ya se ha mencionado, se basa en
el esquema de ‘programación dinámica’. Este método utiliza una tabla para ir
almacenando los resultados correspondientes a instancias más sencillas del
problema a resolver.
No hay comentarios:
Publicar un comentario