L'algorithme de Floyd-Warshall expliqué

Mohammed Islam Hadjoudj

Ingénieur expert en recherche opérationnelle

1. Introduction à l'algorithme de Floyd-Warshall

L'algorithme de Floyd-Warshall résout le problème des plus courts chemins entre toutes les paires. Pour un graphe orienté et pondéré, il détermine la plus courte distance entre chaque paire de sommets, et pas seulement les distances depuis un point de départ choisi. À la fin, vous disposez d'une matrice de distances complète : consultez n'importe quelle origine et n'importe quelle destination, la réponse s'y trouve déjà.

C'est une question différente de celle à laquelle répondent l'algorithme de Dijkstra et celui de Bellman-Ford. Ces derniers sont des algorithmes à source unique : vous leur donnez un sommet de départ et ils vous indiquent la distance de tous les autres sommets à celui-ci. Floyd-Warshall répond à toutes ces questions d'un coup, pour chaque sommet de départ possible, en une seule exécution.

Ce qui rend cet algorithme remarquable, c'est le peu dont il a besoin pour y parvenir. Pas de file de priorité, pas d'ensemble de sommets visités, pas de récursion. L'algorithme entier tient en trois boucles imbriquées sur une matrice, et sa correction repose sur une seule idée claire empruntée à la programmation dynamique. Il accepte en outre les poids d'arêtes négatifs, ce que Dijkstra ne peut pas faire, et il signale la présence d'un cycle négatif comme effet secondaire du travail qu'il effectuait déjà.

2. Toutes les paires ou source unique : pourquoi ne pas répéter Dijkstra ?

Une objection évidente consiste à dire qu'il suffirait d'exécuter un algorithme à source unique une fois depuis chaque sommet. Cette approche est légitime et parfois préférable, il vaut donc la peine de préciser quand chacune l'emporte.

Exécuter l'algorithme de Dijkstra depuis les V sommets, avec un tas binaire, coûte O(V * E log V). Dans un graphe creux, où le nombre d'arêtes E est proche de V, cela revient à environ O(V2 log V), ce qui bat confortablement Floyd-Warshall. Dans un graphe dense, où E approche V2, la même répétition coûte à peu près O(V3 log V), et la borne constante O(V3) de Floyd-Warshall devient la meilleure.

Deux autres considérations tranchent souvent le choix avant même la complexité :

• Poids négatifs. Répéter Dijkstra est tout simplement incorrect dès qu'une arête est négative. Il faudrait lui substituer Bellman-Ford, pour un coût total de O(V2 * E), ou repondérer d'abord le graphe avec l'algorithme de Johnson. Floyd-Warshall accepte directement les arêtes négatives.
• Simplicité. Floyd-Warshall tient en cinq lignes de code environ, sans structure de données annexe. Sur les petits graphes denses courants en ordonnancement, en tables de routage et en programmation compétitive, cette fiabilité vaut mieux qu'un avantage asymptotique.

3. L'idée centrale : les sommets intermédiaires

L'intuition derrière Floyd-Warshall consiste à contraindre le problème d'une manière qui le rende facile à faire croître. Au lieu de demander d'emblée « quel est le plus court chemin de i à j ? », il pose une question plus étroite :

Quel est le plus court chemin de i à j qui n'a le droit de passer, comme escales intermédiaires, que par les sommets d'un certain ensemble autorisé ?

Numérotez les sommets de 1 à V. Définissez l'ensemble autorisé comme les k premiers sommets et notez dk(i, j) la plus courte distance de i à j n'utilisant que {1, 2, ..., k} comme sommets intermédiaires. Les extrémités i et j sont toujours autorisées, qu'elles appartiennent ou non à l'ensemble autorisé. Seuls les sommets strictement intermédiaires sont restreints.

Les deux extrémités de cette définition sont instructives. Lorsque k = 0, rien ne peut servir d'escale, donc d0(i, j) est exactement le poids de l'arête directe de i à j, ou l'infini si une telle arête n'existe pas. Lorsque k = V, tous les sommets sont autorisés, donc dV(i, j) est la véritable distance minimale sans restriction. L'algorithme est la mécanique qui mène de la première à la seconde.

4. La relation de récurrence

Supposons que vous connaissiez déjà toutes les valeurs de dk-1 et que vous vouliez dk. Considérez le plus court chemin de i à j pouvant utiliser {1, ..., k}. Il existe exactement deux possibilités, et elles s'excluent mutuellement :

1. Le chemin n'utilise pas le sommet k. Il n'utilise alors que {1, ..., k-1}, donc sa longueur vaut dk-1(i, j), une valeur que vous possédez déjà.
2. Le chemin utilise le sommet k. Comme un plus court chemin ne répète jamais un sommet, il passe par k exactement une fois. Cela le scinde en un tronçon de i à k et un tronçon de k à j, et aucun des deux ne peut utiliser k comme escale. Sa longueur vaut donc dk-1(i, k) + dk-1(k, j), et ces deux termes sont eux aussi déjà connus.

Le plus court chemin est le plus petit des deux, ce qui donne la récurrence au coeur de l'algorithme :

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

Autrement dit : passer par k ne vaut la peine que si le détour vers k puis vers j est plus court que la meilleure route trouvée sans lui. C'est de la programmation dynamique à l'état pur. Chaque sous-problème est résolu une fois, stocké, puis réutilisé.

En pratique, personne ne stocke V matrices distinctes. Les valeurs peuvent être mises à jour sur place dans une unique matrice V x V, car pendant l'itération k les entrées d(i, k) et d(k, j) ne peuvent pas changer : les mettre à jour exigerait d(k, k), qui vaut 0 tant que le graphe ne contient pas de cycle négatif. Lire une valeur déjà écrasée dans ce même tour est donc sans danger, et l'occupation mémoire tombe de O(V3) à O(V2).

5. Exécution pas à pas

Les récurrences abstraites deviennent claires dès qu'on les fait tourner sur des nombres. Prenons un graphe orienté à quatre sommets avec ces arêtes :

• 1 -> 2 de poids 5
• 1 -> 4 de poids 10
• 2 -> 3 de poids 3
• 3 -> 4 de poids 1

Initialisez la matrice à partir des seules arêtes. La diagonale vaut 0, car chaque sommet s'atteint lui-même sans coût, et toute arête absente vaut l'infini.

k = 0 (arêtes directes seulement)

        1     2     3     4
  1     0     5     inf   10
  2     inf   0     3     inf
  3     inf   inf   0     1
  4     inf   inf   inf   0

Tour k = 1. Le sommet 1 est désormais autorisé comme escale. Toute mise à jour exigerait un d(i, 1) fini, mais la colonne 1 est infinie partout sauf sur la diagonale, car aucune arête ne mène au sommet 1. Rien ne change.

Tour k = 2. Le sommet 2 devient disponible. La ligne 2 offre un d(2, 3) = 3 fini, et la colonne 2 un d(1, 2) = 5 fini. Cela donne une amélioration candidate :

• d(1, 3) valait l'infini. Via le sommet 2, cela devient 5 + 3 = 8. Mis à jour à 8.

Tour k = 3. Le sommet 3 devient disponible, et d(3, 4) = 1. Deux entrées s'améliorent :

• d(1, 4) valait 10 par l'arête directe. Via le sommet 3, cela devient d(1, 3) + d(3, 4) = 8 + 1 = 9. Mis à jour à 9.
• d(2, 4) valait l'infini. Via le sommet 3, cela devient 3 + 1 = 4. Mis à jour à 4.

Remarquez que l'amélioration de d(1, 4) s'est appuyée sur d(1, 3) = 8, une valeur découverte au tour précédent. L'algorithme construit les chemins longs à partir de chemins courts qu'il a déjà démontrés.

Tour k = 4. Le sommet 4 n'a aucune arête sortante, la ligne 4 est donc infinie hors diagonale et aucun chemin ne peut utilement passer par lui. Rien ne change, et l'algorithme se termine.

Résultat (toutes les paires)

        1     2     3     4
  1     0     5     8     9
  2     inf   0     3     4
  3     inf   inf   0     1
  4     inf   inf   inf   0

La réponse pour 1 -> 4 est 9, par la route 1 -> 2 -> 3 -> 4 au coût de 5 + 3 + 1, ce qui bat l'arête directe de poids 10. Les infinis restants sont corrects et non inachevés : aucune arête n'entre dans le sommet 1, donc rien ne peut l'atteindre.

6. Implémentation et pseudo-code

L'algorithme est assez court pour être mémorisé. Le détail qui compte plus que tout autre est l'ordre des boucles.

function FloydWarshall(W, V):
    // W[i][j] = poids de l'arête i -> j, sinon Infinity
    // dist est une matrice V x V

    for i from 1 to V:
        for j from 1 to V:
            dist[i][j] = W[i][j]
        dist[i][i] = 0

    // k DOIT être la boucle la plus externe
    for k from 1 to V:
        for i from 1 to V:
            for j from 1 to V:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

k doit être la boucle la plus externe. C'est de loin la manière la plus courante d'écrire cet algorithme de travers. La récurrence exige que toute paire (i, j) soit mise à jour vis-à-vis du sommet intermédiaire k avant de passer à k + 1. Si k est placée à l'intérieur, la matrice se remplit dans un ordre dépourvu de sens, et le résultat est un ensemble de distances qui paraissent plausibles mais ne sont pas optimales.

Une précaution d'implémentation : si vous représentez l'infini par une grande valeur sentinelle telle que INT_MAX plutôt que par un véritable infini flottant, dist[i][k] + dist[k][j] peut déborder et repasser à un nombre négatif, que la comparaison acceptera volontiers. Utilisez soit un infini réel, soit une garde sur l'addition en sautant la mise à jour dès que l'un des opérandes est la sentinelle.

7. Complexité en temps et en espace

• Temps : O(V3). Trois boucles imbriquées tournant chacune V fois, avec un corps réduit à une comparaison et une affectation. Il n'y a pas de meilleur ni de pire cas qui vaille d'être distingué : l'algorithme effectue exactement V3 tests de relâchement sur toute entrée, quel que soit le nombre réel d'arêtes du graphe.
• Espace : O(V2). Une matrice de distances, mise à jour sur place. Une seconde matrice de même taille est nécessaire si vous voulez aussi reconstruire les chemins.

L'insensibilité à E est le trait déterminant. Un graphe à quatre sommets et trois arêtes coûte autant qu'un graphe à quatre sommets et douze arêtes. C'est du gaspillage sur les graphes creux et parfaitement efficace sur les denses. En contrepartie, la constante est très faible et le schéma d'accès mémoire est régulier et favorable au cache, si bien que Floyd-Warshall dépasse souvent son asymptotique sur des graphes de quelques centaines de sommets.

8. Arêtes négatives et détection des cycles négatifs

Floyd-Warshall accepte les poids d'arêtes négatifs sans la moindre modification. Sa récurrence ne suppose jamais qu'allonger un chemin en augmente la longueur, et c'est précisément cette hypothèse qui fait échouer l'algorithme de Dijkstra sur des entrées négatives.

Les cycles négatifs sont une autre affaire, et aucun algorithme ne peut renvoyer des distances minimales sensées en leur présence : on peut boucler indéfiniment et faire chuter le coût sans borne. Ce que Floyd-Warshall vous offre, c'est un moyen de le remarquer gratuitement. Inspectez la diagonale une fois l'algorithme terminé :

for i from 1 to V:
    if dist[i][i] < 0:
        signaler "cycle négatif détecté"

La diagonale a été initialisée à 0. Un sommet ne peut se retrouver avec une distance négative vers lui-même que s'il existe une marche fermée partant de lui et y revenant dont le poids total est inférieur à zéro, ce qui est exactement la définition d'un cycle négatif. Là où Bellman-Ford a besoin d'un passage supplémentaire dédié sur toutes les arêtes pour établir la même chose, Floyd-Warshall se contente d'un coup d'oeil sur V entrées déjà calculées.

Notez la portée de cette vérification. Elle signale tout cycle négatif auquel le sommet concerné participe. Si la diagonale est saine, chaque distance de la matrice est fiable. Si elle ne l'est pas, les valeurs finies ailleurs dans la matrice doivent être tenues pour dépourvues de sens, et non simplement pour imprécises.

9. Reconstruire les chemins réels

La matrice des distances consigne l'éloignement entre deux sommets, mais pas la route qui y parvient. Retrouver cette route demande une matrice supplémentaire, et le procédé le plus économique stocke, pour chaque paire, le sommet suivant sur le chemin.

Initialisez next[i][j] = j dès qu'une arête directe existe, et laissez la case vide sinon. Ensuite, chaque fois que la boucle principale améliore dist[i][j] en passant par k, héritez du premier pas de la nouvelle route :

if dist[i][k] + dist[k][j] < dist[i][j]:
    dist[i][j] = dist[i][k] + dist[k][j]
    next[i][j] = next[i][k]

L'affectation est next[i][k], et non k. Le premier mouvement du trajet amélioré de i à j est le premier mouvement du trajet de i à k, qui peut fort bien être un tout autre sommet. Relire le chemin devient alors une courte promenade : partez de i, suivez next de proche en proche, et arrêtez-vous en atteignant j. Cela coûte O(V2) d'espace supplémentaire et aucun temps notable.

10. Variantes et applications concrètes

La structure à trois boucles se généralise bien au-delà des plus courts chemins, car la récurrence n'a besoin que d'une opération qui combine deux tronçons et d'une autre qui choisit entre des alternatives.

Fermeture transitive (algorithme de Warshall)

Remplacez l'addition par le ET logique et le minimum par le OU logique, et les mêmes boucles calculent l'accessibilité : l'existence ou non d'un chemin entre chaque paire, indépendamment du coût. C'est le résultat original de Warshall en 1962, et c'est pourquoi l'algorithme combiné porte les deux noms. On le retrouve dans l'analyse de flot de données des compilateurs, dans la résolution de dépendances et dans la planification de requêtes des bases de données.

Chemin le plus large et problèmes de goulot d'étranglement

Remplacez l'addition par le minimum et le minimum par le maximum, et l'algorithme trouve la route dont le maillon le plus étroit est aussi large que possible. C'est la formulation naturelle pour le routage à bande passante maximale dans un réseau et pour la planification de capacité en logistique.

Routage réseau et matrices de latence

Les opérateurs réseau ont souvent besoin d'une matrice complète des latences ou des nombres de sauts entre toutes les paires de noeuds d'une topologie. Les topologies de coeur de réseau sont généralement denses et de taille modeste en sommets, ce qui correspond exactement au régime pour lequel Floyd-Warshall a été conçu.

Arbitrage de devises

Modélisez les devises comme des sommets et les taux de change comme des arêtes. Prendre le logarithme négatif de chaque taux transforme la multiplication des taux en addition de poids, et une boucle d'arbitrage rentable devient un cycle négatif. La vérification de la diagonale indique alors s'il existe une opportunité d'arbitrage, et la matrice next reconstitue la séquence des transactions.

11. Ressources académiques et histoire

L'attribution de cet algorithme est particulièrement enchevêtrée. Plusieurs chercheurs sont parvenus aux mêmes trois boucles indépendamment, à quelques années d'intervalle.

• Stephen Kleene (1956) a décrit la procédure sous-jacente en convertissant des automates finis en expressions régulières, ce qui revient structurellement au même calcul de fermeture.
• Bernard Roy (1959) a publié l'algorithme sous une forme pour l'essentiel moderne dans Transitivité et connexité, trois ans avant les articles qui lui ont donné son nom courant.
• Stephen Warshall (1962) a publié la version de fermeture transitive, démontrant le théorème sur les matrices booléennes qui porte son nom.
• Robert W. Floyd (1962) a publié la version plus court chemin sous forme d'une note remarquablement brève, Algorithm 97: Shortest Path, dans Communications of the ACM.
• Peter Ingerman (1962) a décrit la formulation aujourd'hui standard à trois boucles imbriquées dans la même revue, la même année.

Pour un traitement rigoureux assorti de preuves de correction complètes, la référence standard est Cormen, Leiserson, Rivest et Stein, Introduction to Algorithms, au chapitre consacré aux plus courts chemins entre toutes les paires. Ceux qui comparent les approches pour les graphes creux devraient également étudier l'algorithme de Johnson, qui repondère un graphe de sorte que Dijkstra répété reste valide même en présence d'arêtes négatives. Les références complètes figurent à la fin de cet article.