Floyd Warshall Algorithm

MédioCaminhos mínimos Programação dinâmica

+10

Um grafo direcionado com n nós, numerados de 0 a n-1, é fornecido como uma matriz n por n: matrix[i][j] é o peso da aresta do nó i para o nó j, ou -1 quando não há nenhuma, e matrix[i][i] é 0. O comprimento de um caminho é a soma dos pesos de suas arestas.

Retorne uma matriz n por n cuja entrada [i][j] seja o comprimento do caminho mais curto do nó i ao nó j, ou -1 quando o nó j não puder ser alcançado a partir do nó i.

Função

shortestDistances(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: os pesos das arestas: matrix[i][j] é o peso da aresta de i para j, ou -1 quando não há nenhuma
Retornainteger-2d-array: a menor distância para cada par de nós, -1 onde não há caminho

Restrições

1 ≤ n ≤ 100, em que n = matrix.length = matrix[i].length
matrix[i][i] = 0
Para i ≠ j, matrix[i][j] é -1 (sem aresta) ou 0 ≤ matrix[i][j] ≤ 1000.
As arestas são unidirecionais: matrix[i][j] e matrix[j][i] são independentes.

Exemplos

Entrada: matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
Saída: [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
Explicação: Por meio do nó 1, o nó 0 chega ao nó 2 com custo 6 em vez de 11, e ao nó 3 com custo 9. O nó 1 chega ao nó 0 por meio do nó 2 com custo 3. Nada sai do nó 3, então sua linha é -1 fora da diagonal.

Entrada: matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
Saída: [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
Explicação: A aresta de 2 para 1 tem peso 0, então 0 → 2 → 1 custa 1, menos que o caminho direto de custo 6. Nenhuma aresta sai do nó 1 ou entra no nó 0, então esses pares permanecem -1.

Para ir além

Depois de construir a tabela, uma aresta fica mais barata. Você consegue atualizar todas as distâncias em O(n²) em vez de executar novamente os loops O(n³)?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Você precisa do caminho mais curto para cada par de nós. Floyd-Warshall encontra todas as n² respostas com um único loop triplo. Cada rodada permite que as rotas passem por mais um nó e custa uma comparação por par: a melhor rota até então contra a rota que passa pelo novo nó.

Estenda cada rota por uma aresta até que nada mais mude

Correta, mas não termina nos maiores testes

Intuição

Comece pela matriz e, em cada passagem, estenda cada rota em uma aresta: uma rota de i a m mais a aresta m → j é uma rota de i a j, mantida se for mais curta. Repita até que uma passagem não altere nada.

Após p passagens, toda rota mais curta com até p+1 arestas é encontrada. Nenhum peso é negativo, então alguma rota mais curta não tem ciclo e possui no máximo n-1 arestas, e as passagens param com todas as distâncias finais. Uma passagem corresponde a n³ = 10^6 etapas para 100 nós, e uma longa cadeia de rotas mais curtas exige até n passagens: O(n⁴), até 10^8 etapas.

Algoritmo

Copie matrix para dist.
Para cada i, m e j: se dist[i][m] e matrix[m][j] existirem, calcule a soma deles.
Se dist[i][j] for -1 ou maior que a soma, armazene a soma e lembre-se de que a passagem alterou algo.
Repita a passagem até que ela não altere nada e, em seguida, retorne dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the routes of one edge; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    changed = True
    while changed:
        changed = False
        # One pass: a route from i that ends at m may grow by the edge m -> j.
        for i in range(n):
            for m in range(n):
                if dist[i][m] == -1:
                    continue
                for j in range(n):
                    edge = matrix[m][j]
                    if edge == -1:
                        continue
                    via = dist[i][m] + edge
                    if dist[i][j] == -1 or via < dist[i][j]:
                        dist[i][j] = via
                        changed = True
    return dist

Floyd-Warshall: permita mais uma parada por rodada

Intuição

Limite os nós em que uma rota pode parar entre suas extremidades. A tabela começa como a matriz, com as rotas sem paradas. Após a rodada k, dist[i][j] é a rota mais curta cujas paradas estão todas entre os nós 0 e k, e a última rodada fornece a resposta.

Na rodada k, a melhor rota que também pode parar em k ou pula k, e a tabela já contém essa rota, ou passa por k uma vez, pois nenhum peso é negativo. Suas duas partes param apenas nos nós de 0 a k-1, portanto são dist[i][k] e dist[k][j].

No primeiro exemplo, a rodada 1 substitui a distância direta 11 do nó 0 ao nó 2 por 6. A rodada 2 calcula a distância do nó 0 ao nó 3 como 6 + 3 = 9, com a parada no nó 1 incluída no trecho de distância 6.

Uma tabela é suficiente: a linha k e a coluna k não mudam na rodada k, porque dist[k][k] é 0.

Algoritmo

Copie matrix para dist; -1 significa que nenhuma rota foi encontrada ainda.
Para k de 0 a n-1, e para cada i e j: ignore o par se dist[i][k] ou dist[k][j] for -1.
Caso contrário, calcule via = dist[i][k] + dist[k][j].
Se dist[i][j] for -1 ou maior que via, defina-o como via.
Retorne dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the direct edges; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    # After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == -1:
                continue
            for j in range(n):
                if dist[k][j] == -1:
                    continue
                via = dist[i][k] + dist[k][j]
                if dist[i][j] == -1 or via < dist[i][j]:
                    dist[i][j] = via
    return dist

Armadilhas e casos extremos

Adicionar -1 como se fosse um peso: -1 + 5 = 4 parece uma rota. Verifique primeiro as duas partes e trate -1 em dist[i][j] como pior do que qualquer rota.
Colocar o loop sobre k no interior. As rotas passando pelas paradas de 0 a k-1 precisam estar finalizadas antes que o nó k seja considerado.
Usar o maior int como infinito: somar dois valores causa overflow em um int de 32 bits, resultando em uma distância negativa. Uma distância real é no máximo 99 × 1000 = 99,000, então 10^9 é seguro, pois 2 × 10^9 é menor que 2^31-1.
Presumir que as arestas vão nos dois sentidos. No segundo exemplo, o nó 0 alcança o nó 1, mas o nó 1 não alcança nenhum nó.
Executar uma busca em largura, que ignora os pesos: no primeiro exemplo, ela informa 11 do nó 0 ao nó 2, e não 6.

Perguntas frequentes3

Qual é a complexidade de tempo do algoritmo de Floyd-Warshall?

Tempo O(n³) para n nós: três loops aninhados sobre os nós, com uma adição e uma comparação por etapa, 10^6 etapas para 100 nós. O espaço é O(n²) para a tabela de distâncias, que pode ser atualizada no próprio local.

O Floyd Warshall funciona com pesos negativos nas arestas?

Sim, desde que não haja um ciclo negativo, um ciclo cujos pesos somam menos que 0. Com um ciclo negativo, os caminhos mais curtos não são definidos, e a tabela mostra isso: alguns dist[i][i] terminam abaixo de 0.

Quando você deve usar Floyd Warshall em vez do algoritmo de Dijkstra?

Use Floyd-Warshall para todos os pares de nós em um grafo denso com até algumas centenas de nós. Executar Dijkstra a partir de cada nó custa O(n³) com um array e O(n · E log n) com um heap, o que é mais vantajoso em grafos esparsos grandes. Floyd-Warshall não precisa de heap e aceita arestas negativas, o que Dijkstra não aceita.

def shortestDistances(matrix):
    # Escreva o código aqui

Teste #1

Teste #2

Argumento

matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]

Saída Esperada

[[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]