Optimieren Floyd-Warshall für symmetrische Adjazenzmatrix

Question

Gibt es eine Optimierung dass absenkt der konstante Faktor der Laufzeit von Floyd-Warshall, wenn Sie garantiert eine symmetrische Adjazenzmatrix haben?

Answer 1

Nach einigem Nachdenken kam ich mit:

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

Jetzt natürlich wir beide müssen zeigen, es ist richtig und schneller.

ist Correctness schwieriger zu beweisen, da es auf dem Nachweis von Floyd-Warshall des beruht, die nicht trivial ist. Ein ziemlich guter Beweis ist hier gegeben: Floyd-Warshall Beweis

Die Eingangsmatrix ist symmetrisches . Nun ist der Rest des Beweises verwendet einen modifizierte Floyd-Warshall Beweis zu zeigen, dass die Reihenfolge der Berechnungen in den zwei inneren Schleifen spielt keine Rolle, und dass der Graph Aufenthalte symmetrisch nach jedem Schritt. Wenn wir diese beiden Bedingungen zeigen, sind wahr ist, dann tun beide Algorithmen die gleiche Sache.

Lassen Sie sich dist[i][j][k] als den Abstand von i zu j definiert Verwendung nur mit Ecken aus dem Satz {0, ..., k} als Zwischenscheitelpunkte auf dem Weg von i zu j.

dist[i][j][k-1] ist als das Gewicht der Kante von i zu j definiert. Wenn es keine Kante zwischen diesem Gewicht genommen wird unendlich sein.

Nun die gleiche Logik wie im Beweis verwendet oben verlinkten:

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

Jetzt bei der Berechnung des dist[i][k][k] (und ähnlich für dist[k][i][k]):

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

Da nun dist[k][k][k-1] kann nicht negativ sein (oder wir würden einen negative Schleife in der Grafik), bedeutet dies, dass dist[i][k][k] = dist[i][k][k-1]. Denn wenn dist[k][k][k-1] = 0 dann beiden Parameter gleich sind, andernfalls wird der erste Parameter des min() gewählt wird.

So, jetzt, da dist[i][k][k] = dist[i][k][k-1], wenn dist[i][j][k] Berechnung spielt es keine Rolle, ob dist[i][k] oder dist[k][j] bereits k in ihren Wegen ermöglichen. Da nur dist[i][j][k-1] für die Berechnung des dist[i][j][k] verwendet wird, wird dist[i][j] dist[i][j][k-1] in der Matrix bleiben, bis dist[i][j][k] berechnet wird. Wenn i oder j gleich k dann der oben genannte Fall gilt.

Daher ist die Reihenfolge der Berechnungen spielt keine Rolle.

Jetzt müssen wir diese dist[i][j] = dist[j][i] nach allen Schritten des Algorithmus zeigen.

Wir beginnen mit einem symmetrischen Gitter so dist[a][b] = dist[b][a], für all a und 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]

Daher unsere Aufgabe ist wahr und es wird die unveränderliche, dass dist[a][b] = dist[b][a] zu halten. Daher dist[i][j] = dist[j][i] nach allen Schritten des Algorithmus

Daher ergeben beide Algorithmen das gleiche, zu korrigieren Ergebnis.

ist Geschwindigkeit leichter zu beweisen. Die innere Schleife ist etwas mehr als die Hälfte der Anzahl von Malen aufgerufen es normalerweise genannt wird, so dass die Funktion in etwa doppelt so schnell ist. Nur machte etwas langsamer, weil Sie immer noch die gleiche Anzahl, wie oft zuweisen, aber das spielt keine Rolle, wie min() ist, was die meiste Zeit in Anspruch nimmt.

Wenn Sie etwas falsch mit meinem Beweis zu sehen, aber technisch, können Sie es darauf hinzuweisen, und ich werde versuchen, es zu beheben.

EDIT:

Sie können sowohl Geschwindigkeit und speichern die Hälfte des Speichers durch die Schleife als solche zu ändern:

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

Dies ist nur spaltet die oben für die Schleifen des optimierten Algorithmus, so dass es immer noch richtig ist, und es wird wahrscheinlich die gleiche Geschwindigkeit bekommen, nutzt aber die Hälfte der Speicher.

Dank Chris Elion für die Idee.

Answer 2

(Unter Verwendung der Notation in der Pseudo-Code in Wikipedia-Artikel) Ich glaube (aber nicht getestet), dass, wenn die edgeCost Matrix symmetrisch ist, dann wird der Pfadmatrix auch nach jeder Iteration symmetrisch sein. So müssen Sie nur Update der Hälfte der Einträge bei jeder Iteration.

Auf einer niedrigeren Ebene, nur zum Speichern Hälfte der Matrix müssen (da d (i, j) = d (j, i)), so können Sie die Menge des verwendeten Speichers, reduzieren und verringern hoffentlich die Anzahl der Cache-Misses da Sie die gleichen Daten mehrfach zugreifen zu können.