ArithmétiqueMéthode · Glossaire
algorithme de Floyd
L'algorithme de Floyd est un algorithme de recherche de plus court chemin applicable à un graphe pondéré, relevant de la théorie des graphes. Il permet de déterminer les plus courts chemins entre toutes les paires de sommets du graphe simultanément. Simple à implémenter, il présente cependant un coût algorithmique relativement élevé (complexité cubique en le nombre de sommets). L'algorithme de Moore-Dijkstra, autre méthode de plus court chemin, est plus rapide pour une source unique mais d'une mise en œuvre plus complexe.
Sommaire
Ce que vous allez apprendre
- Suivre la récurrence qui autorise les sommets intermédiaires un à un.
- Vérifier sur quatre sommets pourquoi le coût de A vers D devient 6.
- Distinguer Floyd-Warshall de Moore-Dijkstra et du parcours en largeur.
- Repérer les graphes non connexes et les cycles négatifs.
En clair
Imaginez un réseau de quatre villes, où chaque route porte une durée. Pour connaître le meilleur trajet entre chaque ville de départ et chaque ville d’arrivée, l’algorithme de Floyd tient un carnet de toutes les durées connues. Il autorise les villes intermédiaires une à une. Chaque fois qu’un détour par la nouvelle ville raccourcit un trajet, il remplace l’ancienne durée. À la fin, le même calcul a résolu toutes les paires de villes, et pas seulement les trajets partant d’une ville choisie.
Définition
L’algorithme de Floyd, aussi appelé Floyd-Warshall, calcule les distances minimales entre toutes les paires de sommets d’un graphe pondéré orienté ou non orienté. Une distance initiale vaut 0 d’un sommet à lui-même, le poids de l’arc lorsqu’un arc direct existe, et l’infini en l’absence d’arc direct.
Les sommets sont ensuite admis comme intermédiaires dans un ordre fixé. Pour chaque nouvel intermédiaire, l’algorithme compare la meilleure distance déjà connue entre un départ et une arrivée avec la somme des distances passant par cet intermédiaire. La plus petite des deux valeurs est conservée. Après le passage des n sommets, la matrice contient les distances minimales pour les paires qui ne peuvent exploiter aucun cycle négatif. Le temps de calcul est proportionnel à n3 et la mémoire à n2.
Les poids peuvent être négatifs, contrairement au cadre usuel de l’algorithme de Moore-Dijkstra. En revanche, une paire n’a pas de plus court chemin fini lorsque son sommet de départ peut atteindre un cycle de poids total négatif et que ce cycle peut ensuite atteindre son sommet d’arrivée : parcourir encore ce cycle abaisse indéfiniment le coût. Une valeur diagonale négative à la fin signale un tel cycle.
Le principe
Numérotons les n sommets. La quantité d(k)ij désigne la longueur minimale d’un chemin du sommet i au sommet j dont les sommets intermédiaires appartiennent aux k premiers sommets. À l’étape k, on applique simultanément à chaque paire la règle :
Le premier terme garde le meilleur chemin connu sans passer par k ; le second impose un passage par k. Après l’étape n, d(n)ij donne la distance recherchée, si aucun cycle négatif pertinent ne la rend non finie.
Quand l'utiliser
L’entrée doit être un graphe pondéré fini, orienté ou non, dont les sommets et les poids des arcs sont connus. Les poids s’additionnent le long d’un chemin. L’algorithme produit une distance pour chaque paire atteignable dont le départ ne peut atteindre aucun cycle négatif permettant ensuite de rejoindre l’arrivée ; l’infini demeure lorsqu’aucun chemin ne relie les deux sommets.
Des poids négatifs sont acceptables, à condition qu’aucun cycle négatif ne soit accessible sur la paire étudiée. Par exemple, si B→C pèse −3 et C→B pèse 1, ce cycle pèse −2 : chaque nouveau tour réduit le coût. Il faut alors signaler l’absence de distance minimale, plutôt que lire la matrice comme un ensemble de plus courts chemins. Pour une seule source et des poids tous non négatifs, Moore-Dijkstra évite généralement le calcul de toutes les autres paires.
Un exemple, pas à pas
Considérons quatre sommets A, B, C et D. Les arcs orientés ont pour poids : A→B vaut 3, A→C vaut 10, B→C vaut 1, B→D vaut 7, C→D vaut 2 et D→A vaut 4. La figure met en évidence le chemin qui deviendra optimal de A vers D.
1. Au départ, seules les diagonales et les six liaisons directes ont une valeur finie. Il n’existe notamment aucun arc direct A→D.
2. Quand B devient intermédiaire, le trajet A→B→C coûte 3 + 1 = 4. Il remplace donc l’arc A→C de poids 10. Le trajet A→B→D donne provisoirement 3 + 7 = 10.
3. Quand C devient intermédiaire, A→C→D coûte 4 + 2 = 6 : la valeur de A vers D passe de 10 à 6. De même, B→C→D coûte 1 + 2 = 3 et remplace le poids direct 7.
4. Le résultat de A vers D est donc 6, obtenu par A→B→C→D. Le contrôle se refait directement : 3 + 1 + 2 = 6, valeur inférieure au trajet A→B→D, qui coûte 10, et au trajet A→C→D, qui coûte 12 si l’on conserve l’arc direct A→C.
En pratique
Dans un petit réseau de transport, Floyd-Warshall remplit d’un seul calcul la table des meilleurs coûts entre chaque origine et chaque destination. Si seules quelques origines intéressent l’étude et que tous les poids sont non négatifs, répéter Moore-Dijkstra depuis ces origines économise souvent du temps.
Dans un programme, on conserve aussi une matrice du prochain sommet, ou du prédécesseur, lorsque les itinéraires eux-mêmes sont nécessaires. La matrice des distances seule donne leur coût, mais ne suffit pas à reconstruire la suite des sommets.
Pour vérifier un jeu de contraintes exprimées par des écarts pondérés, la diagonale finale sert de test : une valeur négative révèle un cycle négatif. Si le graphe est très grand et contient peu d’arcs, une méthode conçue pour les graphes creux est généralement préférable à la matrice cubique.
À ne pas confondre
Avec l’algorithme de Moore-Dijkstra. Floyd-Warshall traite toutes les paires et accepte des poids négatifs sans cycle négatif. Moore-Dijkstra part d’une source et suppose des poids non négatifs dans sa forme usuelle. Pour calculer uniquement les distances depuis A dans un grand graphe positif, Moore-Dijkstra est le choix naturel.
Avec le parcours en largeur. Celui-ci minimise le nombre d’arcs dans un graphe non pondéré, ou dont tous les arcs ont le même poids. Dès que des arcs valent 1 et 10, le chemin comportant le moins d’arcs peut ne pas avoir le plus petit poids total.
Limites et pièges
Coût cubique. Avec n sommets, les trois boucles examinent n3 combinaisons et la matrice occupe n2 cases. Doubler n multiplie donc approximativement le nombre d’examens par 8. Sur un grand graphe creux, mieux vaut exploiter la rareté des arcs avec un autre algorithme.
Cycle négatif. Si la diagonale finale contient une valeur strictement négative, un cycle négatif est atteignable depuis le sommet correspondant. Les paires pouvant passer par ce cycle n’ont pas de minimum fini ; il faut les marquer comme telles, et non présenter les nombres calculés comme des distances.
Sommets non reliés. Une valeur infinie n’est ni zéro ni une très grande distance : elle signifie qu’aucun chemin n’existe dans le sens considéré. Dans un graphe orienté, A peut atteindre B sans que B puisse atteindre A. L’implémentation doit préserver l’infini au lieu de l’additionner comme un entier ordinaire.
Chemin non mémorisé. La matrice finale des distances n’énumère pas les arcs du trajet optimal. Si le trajet doit être affiché, il faut mettre à jour en parallèle une matrice de prochains sommets ou de prédécesseurs.
Pour aller plus loin
Le graphe pondéré précise comment des nombres attachés aux arcs représentent longueurs, durées ou coûts, les données mêmes que Floyd-Warshall combine.
L’algorithme de Moore-Dijkstra permet d’étudier l’autre grand choix : partir d’une seule source lorsque les poids sont non négatifs.
L’article Trouver son chemin vite et bien replace la recherche d’itinéraires dans un contexte algorithmique plus large.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres