Algoritmo Floyd – Warshall - Floyd–Warshall algorithm

Algoritmo Floyd – Warshall
Classe Problema de caminho mais curto de todos os pares (para gráficos ponderados)
Estrutura de dados Gráfico
Desempenho de pior caso
Melhor caso de desempenho
Desempenho médio
Pior caso de complexidade de espaço

Em informática , a Floyd-Warshall algoritmo (também conhecida como o algoritmo de Floyd , o algoritmo Roy-Warshall , o algoritmo Roy-Floyd , ou o algoritmo de WFI ) é um algoritmo para encontrar caminhos mais curtos num dirigido gráfico ponderada com flanco positivo ou negativo pesos (mas sem ciclos negativos). Uma única execução do algoritmo encontrará os comprimentos (pesos somados) dos caminhos mais curtos entre todos os pares de vértices. Embora não retorne detalhes dos próprios caminhos, é possível reconstruí-los com modificações simples no algoritmo. Versões do algoritmo também podem ser usadas para encontrar o fechamento transitivo de uma relação , ou (em conexão com o sistema de votação Schulze ) caminhos mais largos entre todos os pares de vértices em um gráfico ponderado.

História e nomenclatura

O algoritmo Floyd – Warshall é um exemplo de programação dinâmica e foi publicado em sua forma atualmente reconhecida por Robert Floyd em 1962. No entanto, é essencialmente o mesmo que os algoritmos publicados anteriormente por Bernard Roy em 1959 e também por Stephen Warshall em 1962 para encontrar o fechamento transitivo de um gráfico, e está intimamente relacionado ao algoritmo de Kleene (publicado em 1956) para converter um autômato finito determinístico em uma expressão regular . A formulação moderna do algoritmo como três loops for aninhados foi descrita pela primeira vez por Peter Ingerman, também em 1962.

Algoritmo

O algoritmo Floyd – Warshall compara todos os caminhos possíveis através do gráfico entre cada par de vértices. Ele é capaz de fazer isso com comparações em um gráfico, embora possa haver até arestas no gráfico, e cada combinação de arestas é testada. Ele faz isso melhorando incrementalmente uma estimativa no caminho mais curto entre dois vértices, até que a estimativa seja ótima.

Considere um gráfico com vértices numerados de 1 a  . Além disso, considere uma função que retorna o caminho mais curto possível de para usando vértices apenas do conjunto como pontos intermediários ao longo do caminho. Agora, dada esta função, nosso objetivo é encontrar o caminho mais curto de cada um para cada um usando qualquer vértice em .

Para cada um desses pares de vértices, o poderia ser

(1) um caminho que não passa (usa apenas vértices no conjunto ).

ou

(2) um caminho que atravessa (de para e depois de para , ambos usando apenas vértices intermediários em  )

Nós sabemos que o melhor caminho a partir de que só utiliza vértices por meio é definida por , e é claro que se houvesse um caminho melhor do que para , em seguida, o comprimento desse caminho seria a concatenação do caminho mais curto a partir de (somente usando vértices intermediários em ) e o caminho mais curto de para (usando apenas vértices intermediários em  ).

Se é o peso da aresta entre os vértices e , podemos definir em termos da seguinte fórmula recursiva : o caso base é

e o caso recursivo é

.

Esta fórmula é o coração do algoritmo Floyd – Warshall. O algoritmo funciona calculando primeiro para todos os pares para , então , e assim por diante. Este processo continua até , e encontramos o caminho mais curto para todos os pares usando quaisquer vértices intermediários. Segue pseudocódigo para esta versão básica:

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j] 
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if

Exemplo

O algoritmo acima é executado no gráfico à esquerda abaixo:

Floyd-Warshall example.svg

Antes da primeira recursão do loop externo, rotulado k = 0 acima, os únicos caminhos conhecidos correspondem às arestas únicas do gráfico. Em k = 1 , os caminhos que passam pelo vértice 1 são encontrados: em particular, o caminho [2,1,3] é encontrado, substituindo o caminho [2,3] que tem menos arestas, mas é mais longo (em termos de peso ) Em k = 2 , os caminhos que passam pelos vértices {1,2} são encontrados. As caixas vermelha e azul mostram como o caminho [4,2,1,3] é montado a partir dos dois caminhos conhecidos [4,2] e [2,1,3] encontrados nas iterações anteriores, com 2 na interseção. O caminho [4,2,3] não é considerado, porque [2,1,3] é o caminho mais curto encontrado até agora de 2 a 3. Em k = 3 , caminhos passando pelos vértices {1,2,3} são encontrados. Finalmente, em k = 4 , todos os caminhos mais curtos são encontrados.

A matriz de distância em cada iteração de k , com as distâncias atualizadas em negrito , será:

k = 0 j
1 2 3 4
eu 1 0 -2
2 4 0 3
3 0 2
4 -1 0
k = 1 j
1 2 3 4
eu 1 0 -2
2 4 0 2
3 0 2
4 -1 0
k = 2 j
1 2 3 4
eu 1 0 -2
2 4 0 2
3 0 2
4 3 -1 1 0
k = 3 j
1 2 3 4
eu 1 0 -2 0
2 4 0 2 4
3 0 2
4 3 -1 1 0
k = 4 j
1 2 3 4
eu 1 0 -1 -2 0
2 4 0 2 4
3 5 1 0 2
4 3 -1 1 0

Comportamento com ciclos negativos

Um ciclo negativo é um ciclo cujas arestas somam um valor negativo. Não há caminho mais curto entre qualquer par de vértices , que fazem parte de um ciclo negativo, porque os comprimentos de caminho de a podem ser arbitrariamente pequenos (negativos). Para uma saída numericamente significativa, o algoritmo Floyd – Warshall assume que não há ciclos negativos. No entanto, se houver ciclos negativos, o algoritmo Floyd – Warshall pode ser usado para detectá-los. A intuição é a seguinte:

  • O algoritmo Floyd – Warshall revisa iterativamente os comprimentos de caminho entre todos os pares de vértices , incluindo onde ;
  • Inicialmente, o comprimento do caminho é zero;
  • Um caminho só pode melhorar se tiver comprimento menor que zero, ou seja, denotar um ciclo negativo;
  • Assim, após o algoritmo, será negativo se houver um caminho de comprimento negativo de volta para .

Portanto, para detectar ciclos negativos usando o algoritmo Floyd – Warshall, pode-se inspecionar a diagonal da matriz de caminho e a presença de um número negativo indica que o gráfico contém pelo menos um ciclo negativo. Durante a execução do algoritmo, se houver um ciclo negativo, números exponencialmente grandes podem aparecer, tão grandes quanto , onde é o maior valor absoluto de uma borda negativa no gráfico. Para evitar problemas de estouro / estouro negativo, deve-se verificar se há números negativos na diagonal da matriz de caminho dentro do loop for interno do algoritmo. Obviamente, em um grafo não direcionado, uma aresta negativa cria um ciclo negativo (isto é, uma caminhada fechada) envolvendo seus vértices incidentes. Considerando todas as arestas do gráfico de exemplo acima como não direcionadas, por exemplo, a sequência de vértices 4 - 2 - 4 é um ciclo com soma de peso -2.

Reconstrução de caminho

O algoritmo Floyd – Warshall normalmente fornece apenas os comprimentos dos caminhos entre todos os pares de vértices. Com modificações simples, é possível criar um método para reconstruir o caminho real entre quaisquer dois vértices do terminal. Embora alguém possa estar inclinado a armazenar o caminho real de cada vértice para cada outro vértice, isso não é necessário e, na verdade, é muito caro em termos de memória. Em vez disso, a árvore do caminho mais curto pode ser calculada para cada nó no tempo usando a memória para armazenar cada árvore, o que nos permite reconstruir com eficiência um caminho a partir de quaisquer dois vértices conectados.

Pseudo-código

let dist be a  array of minimum distances initialized to  (infinity)
let next be a  array of vertex indices initialized to null

procedure FloydWarshallWithPathReconstruction() is
    for each edge (u, v) do
        dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
        next[u][v] ← v
    for each vertex v do
        dist[v][v] ← 0
        next[v][v] ← v
    for k from 1 to |V| do // standard Floyd-Warshall implementation
        for i from 1 to |V|
            for j from 1 to |V|
                if dist[i][j] > dist[i][k] + dist[k][j] then
                    dist[i][j] ← dist[i][k] + dist[k][j]
                    next[i][j] ← next[i][k]
procedure Path(u, v)
    if next[u][v] = null then
        return []
    path = [u]
    while uv
        u ← next[u][v]
        path.append(u)
    return path

Análise

Deixe ser , o número de vértices. Para localizar todos de (para todos e ) dos de requer operações. Desde que começamos com e calcular a seqüência de matrizes , , , , o número total de operações utilizado é . Portanto, a complexidade do algoritmo é .

Aplicações e generalizações

O algoritmo Floyd – Warshall pode ser usado para resolver os seguintes problemas, entre outros:

Implementações

As implementações estão disponíveis para muitas linguagens de programação .

Comparação com outros algoritmos de caminho mais curto

O algoritmo Floyd – Warshall é uma boa escolha para calcular caminhos entre todos os pares de vértices em gráficos densos , nos quais a maioria ou todos os pares de vértices são conectados por arestas. Para gráficos esparsos com pesos de aresta não negativos, a complexidade assintótica mais baixa pode ser obtida executando o algoritmo de Dijkstra de cada vértice inicial possível, uma vez que o tempo de execução do pior caso de Dijkstra repetido ( usando pilhas de Fibonacci ) é menor do que o tempo de execução do Floyd –Algoritmo de Warhall quando é significativamente menor que . Para gráficos esparsos com arestas negativas, mas sem ciclos negativos, o algoritmo de Johnson pode ser usado, com o mesmo tempo de execução assintótico da abordagem repetida de Dijkstra.

Também existem algoritmos conhecidos que usam a multiplicação de matriz rápida para acelerar o cálculo do caminho mais curto de todos os pares em gráficos densos, mas eles normalmente fazem suposições extras sobre os pesos das arestas (como exigir que sejam inteiros pequenos). Além disso, por causa dos altos fatores constantes em seu tempo de execução, eles forneceriam apenas um aumento de velocidade sobre o algoritmo Floyd – Warshall para gráficos muito grandes.

Referências

links externos