Ottimizzare Floyd-Warshall per matrice di adiacenza simmetrica

Question

C'è un'ottimizzazione che abbassa il fattore costante del tempo di esecuzione di Floyd-Warshall, se si sono garantiti per avere una matrice di adiacenza simmetrica?

Answer 1

Dopo qualche pensiero mi si avvicinò con:

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]);

Ora, naturalmente, ci sia bisogno di dimostrare che è corretto e più veloce.

La correttezza è più difficile da provare, dato che si basa sulla prova di Floyd-Warshall di cui non è banale. Una bella buona prova è dato qui: Floyd-Warshall prova

La matrice di ingresso è simmetrica . Il resto della dimostrazione utilizza la prova una versione modificata di Floyd-Warshall per dimostrare che l'ordine dei calcoli nei 2 cicli interni non ha importanza e che il grafico rimane simmetrica dopo ogni passaggio. Se mostriamo entrambe queste condizioni sono vere, allora entrambi gli algoritmi fanno la stessa cosa.

Definiamo dist[i][j][k] come distanza da i a j utilizzando utilizzando solo i vertici dalla {0, ..., k} insieme come vertici intermedi sul percorso da i a j.

dist[i][j][k-1] è definito come il peso del bordo da i a j. Se non ci sono margini tra questo peso è preso per essere infinito.

Ora, usando la stessa logica utilizzata nella dimostrazione linkato sopra:

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

Ora, nel calcolo della dist[i][k][k] (e analogamente per dist[k][i][k]):

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

Ora, poiché dist[k][k][k-1] non può essere negativo (o avremmo un ciclo negativo nel grafico), questo significa che dist[i][k][k] = dist[i][k][k-1]. Poiché se dist[k][k][k-1] = 0 allora entrambi i parametri sono gli stessi, in caso contrario viene scelto il primo parametro del min().

Così ora, perché dist[i][k][k] = dist[i][k][k-1], nel calcolo dist[i][j][k] non importa se dist[i][k] o dist[k][j] già permettono k nei loro percorsi. Poiché dist[i][j][k-1] viene utilizzato solo per il calcolo di dist[i][j][k], dist[i][j] rimarrà dist[i][j][k-1] nella matrice fino dist[i][j][k] viene calcolato. Se i o j uguale k poi il caso di cui sopra si applica.

Pertanto, l'ordine dei calcoli non importa.

Ora abbiamo bisogno di dimostrare che dist[i][j] = dist[j][i] dopo tutte le fasi della procedura.

Si comincia con una griglia simmetrica quindi dist[a][b] = dist[b][a], per tutti 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]

Quindi il nostro compito è vero e manterrà l'invariante che dist[a][b] = dist[b][a]. Pertanto dist[i][j] = dist[j][i] dopo tutti i passaggi dell'algoritmo

Pertanto entrambi gli algoritmi producono lo stesso, corretto, risultato.

La velocità è più facile da dimostrare. L'anello interno è chiamato poco più della metà del numero di volte che viene chiamato normalmente, per cui la funzione è circa due volte più veloce. Appena fatto leggermente più lento perché ancora assegnato lo stesso numero di volte, ma questo non importa come min() è quello che occupa la maggior parte del vostro tempo.

Se vedete qualcosa di sbagliato con la mia prova, tuttavia tecnico, non esitate a farlo notare e cercherò di risolvere il problema.

Modifica

È possibile sia accelerare e salvare metà della memoria modificando il ciclo in quanto tale:

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]);
    }
}

Questa divide proprio in cima alla sopra per cicli dell'algoritmo ottimizzato, quindi è ancora corretto e che sarà probabilmente ottenere la stessa velocità, ma utilizza la metà della memoria.

Grazie a Chris Elion per l'idea.

Answer 2

(Utilizzando la notazione in pseudo-codice nell'articolo Wikipedia) Credo (ma non ancora testato) che se la matrice edgeCost è simmetrica, allora la matrice percorso sarà anche simmetrica dopo ogni iterazione. Così avete solo bisogno di aggiornare la metà delle voci ad ogni iterazione.

Ad un livello inferiore, è sufficiente memorizzare metà della matrice (poiché d (i, j) = d (j, i)), in modo da poter ridurre la quantità di memoria utilizzata, e auspicabilmente ridurre il numero di Cache manca in quanto sarete accedere agli stessi dati più volte.