Optimiser Floyd-Warshall de matrice d'adjacence symétrique

Question

Y at-il une optimisation qui réduit le facteur constant de l'exécution de Floyd-Warshall, si vous êtes assuré d'avoir une matrice de contiguïté symétrique?

Answer 1

Après réflexion, je suis venu avec:

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

nous avons besoin à la fois maintenant bien sûr de montrer qu'il est correct et plus rapide.

est plus difficile à Correctness prouver, car il repose sur la preuve de Floyd-Warshall ce qui est non négligeable. est donnée ici une assez bonne preuve: preuve Floyd-Warshall

La matrice d'entrée est symétrique . Le reste de la preuve utilise la preuve d'un Floyd-Warshall modifié pour montrer que l'ordre des calculs dans les 2 boucles internes n'a pas d'importance et que le graphique reste symétrique après chaque étape. Si nous montrons ces deux conditions sont vraies alors les deux algorithmes font la même chose.

Nous allons définir dist[i][j][k] que la distance de i à j en utilisant en utilisant seulement les sommets de la {0, ..., k} définie comme sommets intermédiaires sur le chemin de i à j.

dist[i][j][k-1] est défini comme le poids du bord de i à j. S'il n'y a pas de bord entre ce poids est considéré comme étant l'infini.

Maintenant, en utilisant la même logique que celle utilisée dans la preuve liée ci-dessus:

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

dans le calcul de dist[i][k][k] (et de même pour dist[k][i][k]):

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

Maintenant, puisque dist[k][k][k-1] ne peut pas être négatif (ou que nous aurions une négative sur le graphique), cela signifie que dist[i][k][k] = dist[i][k][k-1]. Car si dist[k][k][k-1] = 0 alors les deux paramètres sont les mêmes, sinon le premier paramètre du min() est choisi.

Alors maintenant, parce que dist[i][k][k] = dist[i][k][k-1], lors du calcul dist[i][j][k] il ne permet pas d'importance si dist[i][k] ou dist[k][j] déjà k dans leurs chemins. Depuis dist[i][j][k-1] est uniquement utilisé pour le calcul des dist[i][j][k], dist[i][j] restera dist[i][j][k-1] dans la matrice jusqu'à ce que dist[i][j][k] est calculée. Si i ou j égal k alors le cas ci-dessus applique.

Par conséquent, l'ordre des calculs n'a pas d'importance.

Maintenant, nous devons montrer que dist[i][j] = dist[j][i] après toutes les étapes de l'algorithme.

Nous commençons avec une grille symétrique dist[a][b] = dist[b][a] ainsi, pour tous a et 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]

Par conséquent, notre mission est à la fois vrai et il maintiendra l'invariant que dist[a][b] = dist[b][a]. Par conséquent dist[i][j] = dist[j][i] après toutes les étapes de l'algorithme

Par conséquent, les deux algorithmes donnent le même, correct, résultat.

La vitesse est plus facile à prouver. La boucle intérieure est appelée un peu plus de la moitié du nombre de fois où il est normalement appelé, de sorte que la fonction est environ deux fois plus rapide. Juste fait un peu plus lent parce que vous attribuez toujours le même nombre de fois, mais cela n'a pas d'importance que min() est ce qui prend le plus de temps.

Si vous voyez quelque chose de mal avec ma preuve, mais technique, ne hésitez pas à le signaler et je vais essayer de le réparer.

EDIT:

Vous pouvez accélérer à la fois et économiser la moitié de la mémoire en changeant la boucle en tant que tel:

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

Ce que divise ci-dessus pour les boucles de l'algorithme optimisé, il est donc toujours correct et il va probablement obtenir la même vitesse, mais utilise la moitié de la mémoire.

Merci à Chris Elion l'idée.

Answer 2

(En utilisant la notation dans le pseudo-code dans l'article de Wikipedia) Je crois (mais ne l'ai pas testé) que si la matrice edgeCost est symétrique, la matrice de chemin sera également symétrique après chaque itération. Ainsi, il vous suffit de mettre à jour la moitié des entrées à chaque itération.

A un niveau inférieur, il vous suffit de stocker la moitié de la matrice (depuis d (i, j) = d (j, i)), de sorte que vous pouvez réduire la quantité de mémoire utilisée, et l'espoir de réduire le nombre de cache manque puisque vous aurez accès à plusieurs fois les mêmes données.