Introducción
El algoritmo de Floyd-Warshall es un algoritmo de análisis de grafos para que, de forma eficiente y simultanea, 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 mas corto de entre todos los pares de vértices, pero no devuelve los detalles de los caminos en si. El algoritmo es un ejemplo de la Programación Dinámica y su variación mas 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 …ver más…

estos dos caminos cortos son determinados de forma recursiva. Este algoritmo modificado utiliza la misma complejidad de tiempo y espacio que el algoritmo modificado.

¿Dónde se usa?
El algoritmo de Floyd-Warshall puede ser usado para resolver los siguientes problemas, entre otros.
• Caminos corto en un grafo dirigido (Algoritmo de Floyd)
• Clausura transitiva de grafos dirigidos (Algoritmo de Warshall). En el algoritmo original de Warshall, el grafo no tiene aristas con coste o valor y es representado por una matriz Booleana de proximidad. Entonces la operación de suma es remplazada por la aritmética Booleana “AND” y la operación de mínimo es remplazada por “OR”.
• Busqueda de expresiones regulares dependiendo del lenguaje regular aceptado por una autómata finito (Algoritmo de Kleene)
• Inversion de matrices de números reales (Algoritmo de Gauss-Jordan)
• Planeamiento optimo de rutas. En esta aplicación uno esta interesado en encontrar la ruta con el máximo trafico entre dos vértices. Esto significa que, en vez de tomar el minimo, en su lugar uno toma el máximo. El coste de arista representa la constante de flujo. los costes de caminos representan cuellos de botella; asi que la operación de adicion es reemplazada por la operación de minimo.
• Probar si un grafo indirecto es bipartito (Un Grafo bipartito se denomina en Teoría de grafos a un grafo cuyos vértices