Algoritmo de Floyd-Warshall | aplicaciones y generalizaciones

Aplicaciones y generalizaciones

El algoritmo de Floyd-Warshall puede ser utilizado para resolver los siguientes problemas, entre otros:

  • Camino mínimo en grafos dirigidos (algoritmo de Floyd).
  • Cierre transitivo en grafos dirigidos (algoritmo de Warshall). Es la formulación original del algoritmo de Warshall. El grafo es un grafo no ponderado y representado por una matriz booleana de adyacencia. Entonces la operación de adición es reemplazada por la conjunción lógica(AND) y la operación menor por la disyunción lógica (OR).
  • Encontrar una expresión regular dada por un lenguaje regular aceptado por un autómata finito (algoritmo de Kleene).
  • Inversión de matrices de números reales (algoritmo de Gauss-Jordan).
  • Ruta óptima. En esta aplicación es interesante encontrar el camino del flujo máximo entre 2 vértices. Esto significa que en lugar de tomar los mínimos con el pseudocodigo anterior, se coge el máximo. Los pesos de las aristas representan las limitaciones del flujo. Los pesos de los caminos representan cuellos de botella; por ello, la operación de adición anterior es reemplazada por la operación mínimo.
  • Comprobar si un grafo no dirigido es bipartito.
Other Languages