Algoritmo de Floyd-Warshall

Dado um grafo $G$ não-direcionado com pesos nas arestas com $n$ vértices. A tarefa é encontrar o comprimento do caminho mais curto $d_{ij}$ entre cada par de vértices $i$ e $j$.

O grafo pode ter arestas de peso negativo, mas nenhum ciclo negativo (para os ciclos negativos o caminho mais curto é indefinido).

Este algoritmo também pode ser usado para detectar a presença de ciclos negativos. O grafo tem um ciclo negativo se, no final do algoritmo, a distância de um vértice $v$ para ele mesmo for negativa.

Esse algoritmo foi publicado simultaneamente em artigos por Robert Floyd e Stephen Warshall em 1962. Entretanto, em 1959, Bernard Roy publicou essencialmente o mesmo algoritmo, mas sua publicação passou despercebida.

Descrição do algoritmo

A ideia chave do algoritmo é dividir o processo de encontrar o caminho mais curto entre dois vértices para várias fases adcionais.

Iremos numerar os vértices a de 1 até $n$. A matriz de distâncias será $d[ ][ ]$.

Antes da $k$-th fase ($k = 1 \dots n$), $d[i][j]$ para quaisquer vértices $i$ e $j$, o algoritmo armazena o comprimento do caminho mais curto entre o vértice $i$ e o vértice $j$, contendo apenas os vértices $\{1, 2, ..., k-1\}$ como vértices internos dentro do caminho.

Em outras palavras, antes da $k$-th fase, o valor de $d[i][j]$ é igual ao comprimento do caminho mais curto do vértice $i$ para o vértice $j$, se os vértices do caminho forem menores que o valor $k$ (o começo e o final do caminho não são restringidos por essa regra).

Para $k = 0$, podemos preencher a matriz $d[i][j] = w_{i j}$ se existir uma aresta entre $i$ e $j$ com peso $w_{i j}$ e $d[i][j] = \infty$ se não existir uma aresta entre esses vértices. Na prática, $\infty$ será algum valor muito grande. Este é um requisito para o algoritmo.

Suponha agora que estamos na $k$-th fase, e queremos computar a matriz $d[ ][ ]$ para que ela atenda aos requisitos para a $(k + 1)$-th fase. Temos que corrigir as distâncias para alguns pares de vértices $(i, j)$. Existem dois casos fundamentalmente diferentes:

Combinando esses dois casos, descobrimos que podemos recalcular o comprimento de todos os pares $(i, j)$ na $k$-th fase da seguinte maneira:

$$d_{\text{nova distancia}}[i][j] = min(d[i][j], d[i][k] + d[k][j])$$

Portanto, todo o trabalho necessário na $k$-th fase será iterar sobre todos os pares de vértices e recalcular o comprimento do caminho mais curto entre eles. Como resultado, depois da $n$-th fase, o valor $d[i][j]$ na matriz de distância é o comprimento do caminho mais curto entre $i$ e $j$, ou é $\infty$ se o caminho entre os vértices entre $i$ e $j$ não existir.

Uma última observação - não precisamos criar uma matriz de distância separada $d_{\text{new}}[ ][ ]$ para armazenar temporariamente os caminhos mais curtos da $k$-th fase, i.e. todas as alterações podem ser feitas diretamente na matriz $d[ ][ ]$ em qualquer fase. De fato, em qualquer $k$-th fase estamos melhorando a distância de qualquer caminho na matriz de distâncias, assim não podemos piorar o comprimento do caminho mais curto para qualquer par de vértices que devem ser processados na $(k+1)$-th fase ou fases posteriores.

A complexidade deste algoritmo é $O(n^3)$.

Implementação

Deixe que $d[$ $]$$[$ $]$ seja uma array 2D de tamanho $n \times n$, na qual é preenchida de acordo com a $0$-th fase, como explicado anteriormente. Também vamos definir $d[i][i] = 0$ para qualquer $i$ na $0$-th fase(afinal, a distância de um vértice para ele mesmo é zero e será mínima).

Em seguida, o algoritmo é implementado da seguinte maneira:

for (int k = 0; k < n; ++k) {     //iteração das fases do algoritmo
    for (int i = 0; i < n; ++i) {                        //iteração dos vértices
        for (int j = 0; j < n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);      //atualização do caminho mais curto
        }
    }
}

Supõe-se que, se não houver aresta entre dois vértices $i$ e $j$, então a matriz $d[i][j]$ contém um número enorme (sendo maior que qualquer outro comprimento possível no grafo). Então essa aresta sempre será inútil para usar e o algoritmo trabalhará corretamente(esse estágio é semelhante como infinitar as distâncias no algoritmo de Dijkstra).

No entanto, se houver arestas de peso negativas no grafo, medidas especiais deverão ser tomadas. Caso contrário, os valores resultantes na matriz podem ter a forma $\infty - 1$, $\infty - 2$, etc., na qual ainda indica que entre os respectivos vértices não existe um caminho definido. Portanto, se o grafo tiver arestas de peso negativo, é melhor implementar o algoritmo de Floyd-Warshall da seguinte maneira, para que não realize iterações usando caminhos que não existem.

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (d[i][k] < INF && d[k][j] < INF)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

Recuperando a sequência de vértices no caminho mais curto

É fácil manter informações adicionais com as quais será possível recuperar o caminho mais curto entre dois vértices, na forma de uma sequência de vértices.

Para isso, além da matriz de distância $d[ ][ ]$, a matriz de ancestrais $p[ ][ ]$ deve ser mantida, que conterá o número da fase em que a menor distância entre dois vértices foi modificada pela última vez. O número da fase nada mais é do que um vértice no meio do caminho mais curto desejado. Agora só precisamos encontrar o caminho mais curto entre os vértices $i$ e $p[i][j]$, e entre $p[i][j]$ e $j$. Isso leva a um algoritmo de reconstrução recursiva simples do caminho mais curto.

Caso dos pesos reais

Se os pesos das arestas não forem inteiros, mas reais, é necessário levar em consideração os erros que ocorrem ao trabalhar com o tipo float.

O algoritmo de Floyd-Warshall tem o efeito desagradável de acumular os erros rapidamente. De fato, se houver um erro $\delta$ na primeira fase, esse erro pode se propagar para a segunda iteração como $2 \delta$, para a terceira iteração como $3 \delta$, e assim por diante.

Para evitar isso, o algoritmo pode ser modificado para corrigir o erro (E = $\delta$) em consideração usando a seguinte comparação:

if (d[i][k] + d[k][j] < d[i][j] - E)
    d[i][j] = d[i][k] + d[k][j]; 

Caso de ciclos negativos

Formalmente, o algoritmo de Floyd-Warshall não se aplica em grafos que contêm ciclos de pesos negativos. Mas para todos os pares de vértices $i$ e $j$ para o qual não existe um caminho começando em $i$, visitando um ciclo negativo, e terminando em $j$, o algoritmo ainda funcionará corretamente.

Para o par de vértices para os quais a resposta não existe (devido à presença de um ciclo negativo no caminho entre eles), o algoritmo de Floyd armazenará qualquer número (talvez altamente negativo, mas não necessariamente) na matriz de distâncias. No entanto, é possível melhorar o algoritmo de Floyd-Warshall, para tratar com cuidado esses pares de vértices e gerá-los, por exemplo, definidos como $-\text{INF}$.

Isso pode ser feito da seguinte maneira: iremos executar o algoritmo de Floyd-Warshall para um dado grafo. Em seguida, um caminho mais curto entre os vértices $i$ e $j$ não existe se existir um vértice $t$ que é alcançável de $i$ e também por $j$, no qual $d[t][t] < 0$.

Além disso, ao usar o algoritmo de Floyd-Warshall para grafos com ciclos negativos, devemos ter em mente que podem surgir situações nas quais as distâncias podem chegar exponencialmente rápido ao negativo. Portanto, overflow de inteiros deve ser controlado limitando a distância mínima com algum valor (e.g. $-\text{INF}$).

Problemas