Floyd-Warshall für symmetrische Adjazenzmatrix optimieren

Question

Gibt es eine Optimierung, die den konstanten Faktor der Laufzeit von Floyd-Warshall senkt, wenn Sie 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 beide wir müssen sie zeigen, ist richtig und schneller.

Korrektheit ist schwerer zu beweisen, da sie auf dem Beweis von Floyd-Warshall beruht, der nicht trivial ist. Ein ziemlich guter Beweis wird hier gegeben: Floyd-Warshall proof

Die Eingangsmatrix ist symmetric. Nun verwendet der Rest des Beweises einen modifizierten Floyd-Warshall-Beweis, um zu zeigen, dass die Reihenfolge der Berechnungen in den 2 inneren Schleifen keine Rolle spielt und dass das Diagramm nach jedem Schritt symmetrisch bleibt. Wenn wir zeigen, dass beide Bedingungen zutreffen, dann machen beide Algorithmen dasselbe.

die dist[i][j][k] als der Abstand von i zu j unter Verwendung nur mit Eckpunkten aus dem Satz {0, ..., k} als Zwischenscheitelpunkte auf dem Pfad von ij definieren lassen.

dist[i][j][k-1] ist definiert als das Gewicht der Kante von i bis j. Wenn es keine Kante dazwischen gibt, wird dieses Gewicht als unendlich angenommen.

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

nun bei der Berechnung der 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 haben eine negative loop in der Grafik), das bedeutet, dass dist[i][k][k] = dist[i][k][k-1]. Da bei dist[k][k][k-1] = 0 dann beide Parameter gleich sind, wird sonst der erste Parameter der min() gewählt.

So, jetzt, da dist[i][k][k] = dist[i][k][k-1], wenn dist[i][j][k] Berechnung ist es egal, ob dist[i][k] oder dist[k][j] bereits k in ihren Wegen ermöglichen. Da dist[i][j][k-1] nur für die Berechnung von dist[i][j][k] verwendet wird, bleibt 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 ist, dann gilt der obige Fall.

Daher spielt die Reihenfolge der Berechnungen keine Rolle.

Nun müssen wir zeigen, dass dist[i][j] = dist[j][i] nach allen Schritten des Algorithmus.

Wir beginnen mit einem symmetrischen Gitter also dist[a][b] = dist[b][a], für alle 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, korrekte Ergebnis.

Geschwindigkeit ist einfacher zu beweisen. Die innere Schleife wird nur über die Hälfte der Häufigkeit aufgerufen, die normalerweise aufgerufen wird, also ist die Funktion etwa doppelt so schnell. Einfach etwas langsamer gemacht, weil Sie immer noch die gleiche Anzahl von Malen zuweisen, aber das spielt keine Rolle, da min() die meiste Zeit beansprucht.

Wenn Sie irgendetwas falsches mit meinem Beweis sehen, wie technisch auch immer, dann zögern Sie nicht, darauf hinzuweisen und ich werde versuchen, es zu beheben.

EDIT:

Sie können sowohl zu beschleunigen und durch Änderung der Schleife als solche die Hälfte der Speicher speichern:

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 die oben für die Schleifen des optimierten Algorithmus aufspaltet, so Es ist immer noch korrekt und es wird wahrscheinlich die gleiche Geschwindigkeit, aber verwendet die Hälfte des Speichers.

Danke an Chris Elion für die Idee.

Answer 2

(Mit der Notation im Pseudocode im Wikipedia-Artikel) Ich glaube (aber nicht getestet), dass, wenn die edgeCost-Matrix symmetrisch ist, die Pfadmatrix auch nach jeder Iteration symmetrisch sein wird. Daher müssen Sie nur die Hälfte der Einträge bei jeder Iteration aktualisieren.

Auf einer niedrigeren Ebene müssen Sie nur die Hälfte der Matrix speichern (da d (i, j) = d (j, i)), so können Sie die Menge an Speicher reduzieren und hoffentlich die Anzahl reduzieren von Cache-Fehlern, da Sie mehrmals auf dieselben Daten zugreifen.