Optimizar Floyd-Warshall para matriz de adjacência simétrica

Question

Existe uma otimização que reduz o fator constante do tempo de execução de Floyd-Warshall, se você está garantido para ter uma matriz de adjacência simétrica?

Answer 1

Depois de algum pensei que eu vim acima com:

for (int k = 0; k < N; ++k)
    for (int i = 0; i < N; ++i)
        for (int j = 0; j <= i; ++j)
            dist[j][i] = dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

Agora, é claro que ambos necessidade de mostrar que é correto e mais rápido.

A exatidão é mais difícil de provar, uma vez que depende da prova de Floyd-Warshall do que é não-trivial. Um bom prova é dada aqui: Floyd-Warshall prova

A matriz de entrada é simétrica . Ora, o restante da prova usa prova um modificado de Floyd-Warshall para mostrar que a ordem dos cálculos nos 2 loops internos não importa e que o gráfico estadias simétrico após cada passo. Se nós mostrarmos a essas duas condições forem verdadeiras, em seguida, ambos os algoritmos fazer a mesma coisa.

Vamos definir dist[i][j][k] como a distância do i para j usando usando apenas vértices do {0, ..., k} conjunto como vértices intermédios no caminho de i para j.

dist[i][j][k-1] é definido como o peso da aresta de i para j. Se não houver nenhuma vantagem em entre este peso é considerado infinito.

Agora, usando a mesma lógica utilizada na prova ligada acima:

dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1])

Agora, no cálculo do dist[i][k][k] (e similarmente para dist[k][i][k]):

dist[i][k][k] = min(dist[i][k][k-1], dist[i][k][k-1] + dist[k][k][k-1])

Agora, uma vez dist[k][k][k-1] não pode ser negativo (ou teríamos um ciclo negativo no gráfico), isto significa que dist[i][k][k] = dist[i][k][k-1]. Desde se dist[k][k][k-1] = 0 então ambos os parâmetros são os mesmos, caso contrário, o primeiro parâmetro do min() é escolhido.

Então, agora, porque dist[i][k][k] = dist[i][k][k-1], ao calcular dist[i][j][k] não importa se dist[i][k] ou dist[k][j] já permitem k em seus caminhos. Desde dist[i][j][k-1] só é utilizado para o cálculo do dist[i][j][k], dist[i][j] vai ficar dist[i][j][k-1] na matriz até dist[i][j][k] é calculado. Se i ou j igual k então o caso acima se aplica.

Portanto, a ordem dos cálculos não importa.

Agora precisamos mostrar que dist[i][j] = dist[j][i] depois de todos os passos do algoritmo.

Começamos com uma grade simétrica, assim, dist[a][b] = dist[b][a], para todos a e b.

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
           = min(dist[j][i], dist[k][i] + dist[j][k])
           = min(dist[j][i], dist[j][k] + dist[k][i])
           = dist[j][i]

Portanto, nossa tarefa é verdade e ele vai manter a invariante que dist[a][b] = dist[b][a]. Portanto dist[i][j] = dist[j][i] depois de todos os passos do algoritmo

Portanto, ambos os algoritmos de produzir o mesmo, correcta, resultado.

A velocidade é mais fácil de provar. O loop interno é chamado de pouco mais de metade do número de vezes que é normalmente chamado, então a função é de cerca de duas vezes mais rápido. Acaba de fazer um pouco mais lento, porque você ainda atribuir o mesmo número de vezes, mas isso não importa, min() é o que ocupa a maior parte do seu tempo.

Se você vê errado alguma coisa com a minha prova, no entanto técnica, fique à vontade para indicá-lo e eu vou tentar corrigi-lo.

EDIT:

Você pode tanto acelerar e salvar metade da memória, alterando o ciclo como tal:

for (int k = 0; k < N; ++k) {
    for (int i = 0; i < k; ++i)
        for (int j = 0; j <= i; ++j)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[j][k]);
    for (int i = k; i < N; ++i) {
        for (int j = 0; j < k; ++j)
            dist[i][j] = min(dist[i][j], dist[k][i] + dist[j][k]);
        for (int j = k; j <= i; ++j)
            dist[i][j] = min(dist[i][j], dist[k][i] + dist[k][j]);
    }
}

Isso só divide-se acima para loops do algoritmo otimizado, por isso ainda é correto e ele provavelmente vai ter a mesma velocidade, mas usa metade da memória.

Graças à Chris Elion para a idéia.

Answer 2

(Usando a notação do pseudo-código no artigo Wikipedia) Eu acredito (mas não testei) que, se a matriz edgeCost é simétrica, então a matriz de caminhos também será simétrica após cada iteração. Assim, você só precisa de atualização metade das entradas a cada iteração.

Em um nível inferior, você só precisa armazenar metade da matriz (uma vez que d (i, j) = d (j, i)), para que você possa reduzir a quantidade de memória utilizada, e esperamos reduzir o número de erros de cache uma vez que você acessar os mesmos dados várias vezes.