Algoritmo de Floyd-Warshall
Origem: Wikipédia, a enciclopédia livre.
Na ciência da computação, o algoritmo de Floyd-Warshall (às vezes chamado de algoritmo de Roy-Floyd ou algoritmo de Warshall) é 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). Sua complexidade é cúbica.
Índice |
[editar] Algoritmo
O algoritmo de Floyd-Warshall recebe como entrada uma matriz de adjacências que representa um grafo (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 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 (i.e., de menor custo) de todos os caminhos entre os vértices. Sua ordem de complexidade é Θ(|V|3).
O algoritmo se baseia nos passos abaixo:
- Assumindo que os vértices de um grafo orientado G são V = {1,2,3,...,n}, considere um subconjunto {1,2,3,...,k};
- Para qualquer par de vértices (i, j) em V, considere todos os caminhos de i a j cujos vértices intermediários pertencem ao subconjunto {1,2,3,...,k}, e p como o mais curto de todos eles;
- O algoritmo explora um relacionamento entre o caminho p e os caminhos mais curtos de i a j com todos os vértices intermediários em {1,2,3,...,k−'};
- O relacionamento depende de k ser ou não um vértice intermediário do caminho p.
Abaixo segue uma implementação em pseudo-código do algoritmo de Floyd-Warshall:
function fw(int[1..n,1..n] graph) { // Initialization var int[1..n,1..n] dist := graph var int[1..n,1..n] pred for i from 1 to n for j from 1 to n if dist[i,j] < Infinity pred[i,j] := i // Main loop of the algorithm for k from 1 to n for i from 1 to n for j from 1 to n if dist[i,j] > dist[i,k] + dist[k,j] dist[i,j] = dist[i,k] + dist[k,j] pred[i,j] = pred[k,j] return dist }
[editar] Aplicações
O algoritmo de Floyd-Warshall pode ser utilizado para resolver os problemas abaixo:
- Caminhos mais curtos em grafos orientados (algoritmo de Floyd). Para isto 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 (AND) e a operação de subtração por disjunção lógica(OR);
- 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). Veja o exemplo de implementação em Python para detalhes;
- Roteamento otimizado. Nesta aplicação, alguém está interessado em encontrar o caminho com o máximo fluxo entre dois vértices. Isto significa que, em vez de calcular o mínimo no pseudo-código acima, calcula-se o máximo. Os pesos da aresta representa contantes 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.
[editar] Implementações
- Uma implementação em Perl está disponível em Graph;
- Uma implementação em Javascript está disponível em Alex Le's Blog