L'algorithme de Floyd–Warshall

Les vieux atlas routiers avaient un tableau à la fin : la distance entre chaque paire de villes. Floyd–Warshall permet de calculer un tel tableau, et c'est l'un des algorithmes les plus courts jamais écrits : trois boucles, une comparaison, et chaque plus courte distance se met en place.

Un petit graphe dont les arêtes ont des longueurs, à côté d'un tableau des distances entre chaque paire de nœuds, avec une ligne et une colonne mises en évidence
Un petit graphe dont les arêtes ont des longueurs, à côté d'un tableau des distances entre chaque paire de nœuds, avec une ligne et une colonne mises en évidence

L'idée

L'algorithme de Dijkstra et Bellman–Ford trouvent les plus courtes distances depuis un seul départ. Floyd–Warshall les trouve d'un coup de chaque nœud vers tous les autres, dans un tableau avec une ligne et une colonne par nœud. Il part de ce que disent directement les arêtes, puis améliore tout le tableau en autorisant de plus en plus de nœuds comme escales en chemin.

Pas à pas

Remplissez le tableau : 0 de chaque nœud à lui-même, la longueur de l'arête entre voisins, et l'infini ailleurs. Puis, pour chaque nœud k et pour chaque paire i, j : si la distance de i à k plus la distance de k à j est plus petite que la distance de i à j, inscrivez le plus petit nombre. C'est tout l'algorithme. En code, ce sont trois boucles, avec k à l'extérieur.

Un exemple

Prenez quatre nœuds avec les arêtes A–B de longueur 3, B–C 1, A–C 5 et C–D 2. Le tableau part de ces valeurs, avec l'infini pour A–D et B–D. Le tour A ne change rien, car tout chemin par A est plus long. Le tour B trouve A à C par B : 3 + 1 = 4, plus court que 5. Le tour C trouve A à D par C : 4 + 2 = 6, et B à D : 1 + 2 = 3, les deux premiers chemins trouvés. Le tour D ne change rien. Le tableau final : A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.

Pourquoi l'ordre des boucles compte

L'escale k doit être la boucle extérieure. Après le tour de k, chaque case est la plus courte distance qui n'utilise comme escales que les k premiers nœuds, et le tour suivant s'appuie dessus : un meilleur chemin par la nouvelle escale est un meilleur chemin jusqu'à elle plus un meilleur chemin depuis elle, tous deux déjà justes. Mettre k dans une boucle intérieure casse cette garantie et peut laisser des distances fausses. Mettre à jour le tableau sur place pendant un tour est sans risque, car la ligne et la colonne de k ne changent pas pendant ce tour.

Histoire et usages

Bernard Roy a décrit la méthode en 1959. En 1962, Stephen Warshall l'a publiée pour la fermeture transitive, qui demande seulement si un nœud peut en atteindre un autre, et Robert Floyd pour les plus courts chemins. Elle calcule des tableaux de distances et des tables de routage, trouve le diamètre d'un réseau, indique quels nœuds peuvent atteindre lesquels, et, avec une case négative sur la diagonale, révèle un cycle négatif.

À vous d'essayer

Ouvrez l'application et appuyez sur Étape. Le graphe est d'un côté, le tableau de l'autre. Chaque tour met en évidence la ligne et la colonne de l'escale actuelle ; chaque étape inscrit la distance plus courte d'une paire et entoure les deux cases additionnées. Les cases modifiées pendant ce tour sont teintées. Choisissez un départ et une cible pour voir le plus court chemin entre eux quand le tableau est complet.

Questions fréquemment posées

Quelle est la complexité de Floyd–Warshall ?

O(n³) pour n nœuds, quel que soit le nombre d'arêtes, et O(n²) de mémoire pour le tableau. C'est la méthode de choix pour les graphes petits ou denses, où sa boucle simple tourne très vite.

Floyd–Warshall ou Dijkstra depuis chaque nœud ?

Pour un graphe dense, ou quand des arêtes peuvent être négatives, Floyd–Warshall est plus simple et à peu près aussi rapide. Pour un grand graphe peu dense aux arêtes positives ou nulles, lancer l'algorithme de Dijkstra depuis chaque nœud est plus rapide.

Floyd–Warshall relève-t-il de la programmation dynamique ?

Oui. Il résout le problème pour les chemins dont les escales sont parmi les k premiers nœuds à l'aide des réponses pour les k − 1 premiers, et ne garde qu'un seul tableau, qu'il écrase au fur et à mesure.

Qu'est-ce que la fermeture transitive ?

Le tableau qui dit quels nœuds peuvent atteindre lesquels, sans tenir compte des distances. La version de Warshall le calcule avec « ou » et « et » au lieu de « min » et « + ».

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Essayer Floyd–Warshall