Floyd-Warshall est un algorithme de graphes qui calcule les plus courts chemins entre toutes les paires de sommets. Contrairement à Dijkstra, qui part d’un sommet donné, Floyd-Warshall produit une matrice complète : distance de chaque sommet vers chaque autre sommet.
Il est utile quand le graphe est de taille modérée et que l’on veut répondre ensuite rapidement à beaucoup de questions de distance.
La réponse courte
Floyd-Warshall repose sur une idée de programmation dynamique :
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
Pour chaque sommet intermédiaire k, on teste si passer par k améliore le trajet de i vers j.
Complexité :
| Mesure | Valeur |
|---|---|
| Temps | O(n³) |
| Mémoire | O(n²) |
| Type de résultat | plus courts chemins entre toutes les paires |
n est le nombre de sommets.
Quand utiliser Floyd-Warshall
Floyd-Warshall est pertinent si :
- le graphe n’est pas trop grand ;
- vous voulez toutes les distances, pas seulement depuis un sommet ;
- le graphe peut contenir des poids négatifs, mais pas de cycle négatif ;
- la représentation matricielle est pratique pour votre problème.
Si vous voulez seulement le plus court chemin depuis un sommet, Dijkstra en Python est souvent plus adapté.
Implémentation simple en Python
On part d’une liste de sommets et d’arêtes pondérées.
def floyd_warshall(sommets, aretes):
infini = float("inf")
distances = {
i: {j: infini for j in sommets}
for i in sommets
}
for sommet in sommets:
distances[sommet][sommet] = 0
for depart, arrivee, poids in aretes:
distances[depart][arrivee] = min(distances[depart][arrivee], poids)
for intermediaire in sommets:
for depart in sommets:
for arrivee in sommets:
nouveau = distances[depart][intermediaire] + distances[intermediaire][arrivee]
if nouveau < distances[depart][arrivee]:
distances[depart][arrivee] = nouveau
return distances
sommets = ["A", "B", "C", "D"]
aretes = [
("A", "B", 3),
("A", "C", 10),
("B", "C", 2),
("C", "D", 1),
("B", "D", 7),
]
distances = floyd_warshall(sommets, aretes)
print(distances["A"]["D"])
Ici, le chemin A -> B -> C -> D est plus court que A -> B -> D ou A -> C -> D.
Reconstruire les chemins
Calculer la distance est utile, mais on veut parfois connaître le chemin.
Pour cela, on garde une matrice suivant.
def floyd_warshall_chemins(sommets, aretes):
infini = float("inf")
distances = {i: {j: infini for j in sommets} for i in sommets}
suivant = {i: {j: None for j in sommets} for i in sommets}
for sommet in sommets:
distances[sommet][sommet] = 0
suivant[sommet][sommet] = sommet
for depart, arrivee, poids in aretes:
distances[depart][arrivee] = poids
suivant[depart][arrivee] = arrivee
for k in sommets:
for i in sommets:
for j in sommets:
nouveau = distances[i][k] + distances[k][j]
if nouveau < distances[i][j]:
distances[i][j] = nouveau
suivant[i][j] = suivant[i][k]
return distances, suivant
def reconstruire(suivant, depart, arrivee):
if suivant[depart][arrivee] is None:
return None
chemin = [depart]
while depart != arrivee:
depart = suivant[depart][arrivee]
chemin.append(depart)
return chemin
distances, suivant = floyd_warshall_chemins(sommets, aretes)
print(reconstruire(suivant, "A", "D"))
Cette version est plus complète, mais elle demande aussi plus de mémoire.
Détecter un cycle négatif
Floyd-Warshall accepte les arêtes de poids négatif, mais pas les cycles négatifs. Un cycle négatif rend la notion de plus court chemin instable : on peut tourner dans le cycle pour réduire le coût indéfiniment.
Après l’algorithme, si une distance distances[sommet][sommet] devient négative, il existe un cycle négatif accessible.
def contient_cycle_negatif(distances):
return any(distances[s][s] < 0 for s in distances)
Floyd-Warshall, Dijkstra ou BFS
| Besoin | Algorithme recommandé |
|---|---|
| Plus court chemin non pondéré | BFS |
| Plus court chemin depuis un sommet, poids positifs | Dijkstra |
| Plus court chemin vers une cible avec heuristique | A* |
| Plus courts chemins entre toutes les paires | Floyd-Warshall |
| Arbre couvrant minimum | Prim ou Kruskal |
Cette distinction évite beaucoup d’erreurs. Floyd-Warshall n’est pas “meilleur” que Dijkstra : il répond à une autre question.
Erreurs fréquentes
La première erreur est d’utiliser Floyd-Warshall sur un très grand graphe. O(n³) devient vite coûteux.
La deuxième erreur est de mal initialiser la diagonale. La distance d’un sommet vers lui-même doit commencer à 0.
La troisième erreur est d’oublier que le graphe peut être orienté. Si une arête va de A vers B, cela ne veut pas dire qu’elle va aussi de B vers A.
La quatrième erreur est d’ignorer les cycles négatifs. Si votre graphe contient des coûts négatifs, vérifiez la diagonale après calcul.
Où continuer
Floyd-Warshall complète le cluster graphes :
- Algorithmes Python : tous les guides pour apprendre pas à pas
- Algorithmes de graphes en Python
- BFS et DFS en Python
- Algorithme A* en Python
- Complexité algorithmique en Python
La règle à retenir : utilisez Floyd-Warshall quand vous voulez toutes les distances entre toutes les paires de sommets et que le graphe reste assez petit pour supporter un coût en O(n³).
