ALGORITMO FLOYD WARSHALL ¿QUE HACE?

En informática, el algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, 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.

Floy-Warshall como programación dinámica

El algoritmo de Floyd-Warshall es un ejemplo de programación dinámica. El algoritmo de Floyd-Warshall 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 funciona?

Sea un grafo G con conjunto de vértices V, numerados de 1 a N. Sea además una función caminoMinimo(i,j,k) que devuelve el camino mínimo de i a j usando únicamente los vértices de 1 a k como puntos intermedios en el camino. Ahora, dada esta función, nuestro objetivo es encontrar el camino mínimo desde cada i a cada j usando únicamente los vértices de 1 hasta k+ 1. Hay dos candidatos para este camino: un camino mínimo, que utiliza únicamente los vértices del conjunto (1...k); o bien existe un camino que va desde i hasta k + 1, después de k + 1hasta j que es mejor.

Sabemos que el camino óptimo de i a j que únicamente utiliza los vértices de 1 hasta k está definido por caminoMinimo(i,j,k), y está claro que si hubiera un camino mejor de i a k + 1 a j, la longitud de este camino sería la concatenación del camino mínimo de i a k + 1 (utilizando vértices de (1...k)) y el camino mínimo de k + 1 a j (que también utiliza los vértices en (1...k)).   Esta fórmula es la base del algoritmo Floyd-Warshall. Funciona ejecutando primero caminoMinimo(i,j,1) para todos los pares (i,j), usándolos para después hallar caminoMinimo(i,j,2) para todos los pares (i,j)...

Este proceso continúa hasta que k = n, y habremos encontrado el camino más corto para todos los pares de vértices (i,j) usando algún vértice intermedio.    

BIOGRAFÍA DE SUS CREADORES

Bernard Roy (nacido en 1934), es profesor emérito de la Universidad Paris-Dauphine.  En 1974 se fundó el "Laboratoire d'Analyse et de modelización des Systèmes pour l'aide à la Decisión" (LAMSADE). Ha trabajado en la teoría de grafos y el análisis de decisión multicriterio (MCDA), habiendo creado el ELECTRE familia de métodos. El nombre ELECTRE significa "Eliminación Et Choix Traduisant la Réalité".

Robert W. Floyd (8 de junio de 1936 - 25 de septiembre de 2001) fue un prominente científico estadounidense en informática. Nacido en Nueva York, Floyd culminó el bachillerato a los 14 años. Se graduó en la Universidad de Chicago en 1953 a los 17 años y como Físico en 1958.   Operador de computadoras en los años 60, publicó sus primeros artículos los cuales fueron de gran influencia y fue nombrado profesor asociado en la Universidad de Carnegie Mellon. Seis años más tarde fue nombrado profesor en la Universidad de Stanford.   Entre sus contribuciones se encuentran el diseño y análisis de algoritmos eficientes para encontrar el camino más corto en un grafo y para el problema de reconocimiento de frases, pero probablemente su logro más importante fue el ser pionero, con su artículo de 1967 «Assigning Meanings to Programs», en el área de verificación de programas utilizando aserciones lógicas, donde aparece la importante noción de invariante, esencial para demostrar propiedades de programas iterativos.

Floyd recibió el Premio Turing de la ACM en 1978 «por tener una clara influencia en las metodologías para la creación de software eficiente y confiable, y por haber contribuido a la fundación de las subáreas teoría del reconocimiento de frases, semántica de los lenguajes de programación, verificación automatizada de programas, síntesis automatizada de programas y análisis de algoritmos».

Stephen Warshall (15 noviembre 1935 a 11 diciembre 2006) nació en New York City. Durante su carrera, Warshall llevado a cabo la investigación y el desarrollo de sistemas operativos, diseño, diseño del compilador del lenguaje, y la investigación operativa. Warshall murió el 11 de diciembre de 2006 de cáncer en su casa de Gloucester, Massachusetts. Le sobreviven su esposa, Sarah Dunlap, y dos hijos, Andrew D. Warshall y Santa VZ Warshall.    

Educación

Warshall fue a la escuela pública en Brooklyn. Se graduó de A.B. Davis High School en Mount Vernon, Nueva York y asistió a la Universidad de Harvard, recibiendo una licenciatura en matemáticas en 1956. Nunca recibió un grado avanzado ya que en ese momento no estaban disponibles en los programas de sus áreas de interés. Sin embargo, tomó cursos de postgrado en varias universidades y ha contribuido al desarrollo de la informática y la ingeniería de software. En el año académico 1971-1972, fue profesor en la ingeniería de software en las universidades francesas.  

¿Que hace o para que sirve el algoritmo Floyd Warshall?

En el siguiente vídeo se explica de manera clara y detallada el funcionamiento del algoritmo Warshall. Es un paso a paso detallado para entender cómo funciona el algoritmo.

Algoritmo Warshall

Hay una anécdota interesante de su prueba de que el algoritmo de clausura transitiva, ahora conocido como algoritmo de Warshall, es correcto. Él y un colega de Operaciones Técnicas apuesto una botella de ron en el primero que podría determinar si este algoritmo siempre funciona. Warshall se acercó con su prueba durante la noche, ganando la apuesta y el ron, el cual compartió con el perdedor de la apuesta. Porque Warshall no le gustaba sentarse en un escritorio, hizo gran parte de su trabajo creativo en lugares no convencionales, como en un velero en el Océano Índico o en un huerto de limón griego.

Si quieres conocer otros artículos parecidos a ALGORITMO FLOYD WARSHALL ¿QUE HACE? puedes visitar la categoría Programación.