Algoritmo de Floyd-Warshall
Na ciência da computação, o algoritmo de Floyd-Warshall (também conhecido como: Floyd's algorithm, Roy–Warshall algorithm, Roy–Floyd algorithm, ou WFI algorithm) é um algoritmo que resolve o problema de calcular o caminho mais curto entre todos os pares de vértices em um grafo orientado (com direção) e valorado (com peso). 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.[1] O formato atual do algoritmo de Floyd-Warshall com três loops de repetição foi descrito por Peter Ingerman em 1962.
O algoritmo é um bom exemplo de programação dinâmica.
Definição
[editar | editar código-fonte]O algoritmo de Floyd-Warshall recebe como entrada uma matriz de adjacência que representa um grafo 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 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 é .
O algoritmo se baseia nos passos abaixo:
- Assumindo que os vértices de um grafo orientado são , considere um subconjunto ;
- Para qualquer par de vértices em , considere todos os caminhos de a cujos vértices intermédios pertencem ao subconjunto , e como o mais curto de todos eles;
- O algoritmo explora um relacionamento entre o caminho e os caminhos mais curtos de a com todos os vértices intermédios em ;
- O relacionamento depende de ser ou não um vértice intermédio do caminho .
Abaixo segue uma implementação em pseudocódigo do algoritmo de Floyd-Warshall:
ROTINA fw(Inteiro[1..n,1..n] grafo) # Inicialização VAR Inteiro[1..n,1..n] dist := grafo VAR Inteiro[1..n,1..n] pred PARA i DE 1 A n PARA j DE 1 A n SE dist[i,j] < Infinito ENTÃO pred[i,j] := i # Laço principal do algoritmo PARA k DE 1 A n PARA i DE 1 A n PARA j DE 1 A n SE dist[i,j] > dist[i,k] + dist[k,j] ENTÃO dist[i,j] = dist[i,k] + dist[k,j] pred[i,j] = pred[k,j] RETORNE dist
Aplicações
[editar | editar código-fonte]O algoritmo de Floyd-Warshall pode ser utilizado para resolver os problemas abaixo:
- Caminhos mais curtos em grafos orientados (algoritmo de Floyd). Para funcionar, os valores de todas as arestas são configurados para o mesmo número positivo. Esse número é normalmente escolhido como único, tanto é que o valor de um caminho coincide com o número de arestas ao longo desse caminho;
- Proximidade transitiva de grafos orientados (algoritmo de Warshall). Na formulação original deste último, o grafo se torna desvalorado (perde valores) e é representado por uma matriz booleana de adjacência. Depois, a operação de soma é substituída por conjunção lógica (E) e a operação de subtração por disjunção lógica (OU);
- Encontrar uma expressão regular denotando a linguagem regular aceita por um autômato finito (algoritmo de Kleene);
- Inversões de matrizes de números reais (algoritmo de Gauss-Jordan);
- Roteamento otimizado. Nesta aplicação, o interesse é encontrar o caminho com o máximo fluxo entre dois vértices. Isto significa que, em vez de calcular o mínimo no pseudocódigo acima, calcula-se o máximo. Os pesos das arestas representam constantes fixas de fluxo. Valores do caminho representam gargalos, logo a operação de soma acima é substituída pela operação de subtração;
- Testar se um grafo não-orientado é bipartido.[1]
Referências
- ↑ Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8. Section 26.2, "The Floyd–Warshall algorithm", pp. 558–565; Section 26.4, "A general framework for solving path problems in directed graphs", pp. 570–576.
Ligações externas
[editar | editar código-fonte]- Algoritmo de Floyd-Warshall em C++ [1]