Presentación sobre El algoritmo de Warshall

Presentación

• 
• Presentado Por :
• Jorge Velásquez 1-741-2173
• Norman Suira 4-794-2493

Algoritmo de Warshall

• En informática, el algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmode 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-Warshall es un ejemplo de programación dinámica.
• 

¿En qué consisten el A. de Warshall?

• 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 vera volcado en la matriz final.
• 

Código de un Ejemplo de Warshall