Algoritmo de Floyd-Warshall
Na ciência da computação, o algoritmo de Floyd-Warshall é um algoritmo que resolve o problema de calcular o caminho mais curto entre todos os pares de vértices em um grafo orientado e valorado. O algoritmo Floyd-Warshall foi publicado por Robert Floyd em 1962. Este algoritmo é o mesmo que foi publicado por Bernard Roy em 1959 e também por Stephen Warshall em 1962 para determinar o fechamento transitivo de um grafo. O formato atual do algoritmo de Floyd-Warshall com três loops de repetição foi descrito por Peter Ingerman em 1962.
O algoritmo de Floyd-Warshall recebe como entrada uma matriz de adjacência que representa um grafo ( V , E ) {\displaystyle (V,E)} orientado e valorado. O valor de um caminho entre dois vértices é a soma dos valores de todas as arestas ao longo desse caminho. As arestas E {\displaystyle E} do grafo podem ter valores negativos, mas o grafo não pode conter nenhum ciclo de valor negativo. O algoritmo calcula, para cada par de vértices, o menor de todos os caminhos entre os vértices. Por exemplo, o caminho de menor custo. Sua ordem de complexidade é Θ ( | V | 3 ) {\displaystyle \Theta (|V|^{3})} . O algoritmo se baseia nos passos abaixo: Abaixo segue uma implementação em pseudocódigo do algoritmo de Floyd-Warshall:
O algoritmo de Floyd-Warshall pode ser utilizado para resolver os problemas abaixo:
