Algorithme de Floyd-Warshall

Algorithme de Floyd-Warshall
Découvreur ou inventeur
Date de découverte
Problèmes liés
Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (en)Voir et modifier les données sur Wikidata
Structure des données
Complexité en temps
Pire cas
O(|S|3)Voir et modifier les données sur Wikidata
Moyenne
O(|S|3)Voir et modifier les données sur Wikidata
Meilleur cas
O(|S|3)Voir et modifier les données sur Wikidata
Complexité en espace
Pire cas
O(|S|2)Voir et modifier les données sur Wikidata

En informatique, l'algorithme de Floyd-Warshall est un algorithme pour déterminer les distances des plus courts chemins entre toutes les paires de sommets dans un graphe orienté et pondéré, en temps cubique au nombre de sommets. Il est parfois appelé algorithme de Roy-Floyd-Warshall car il a été décrit par Bernard Roy en 1959 avant la parution des articles de Floyd et Warshall datant de 1962.

Algorithme

L'algorithme de Floyd-Warshall prend en entrée un graphe orienté et valué, décrit par une matrice d'adjacence donnant le poids d'un arc lorsqu'il existe et la valeur ∞ sinon. Le poids d'un chemin entre deux sommets est la somme des poids sur les arcs constituant ce chemin. Les arcs du graphe peuvent avoir des poids négatifs, mais le graphe ne doit pas posséder de circuit de poids strictement négatif. L'algorithme calcule, pour chaque paire de sommets, le poids minimal parmi tous les chemins entre ces deux sommets.

L'algorithme de Floyd-Warshall est un exemple de programmation dynamique. Soit G=(S,A) un graphe à n sommets avec S={s1,s2,…,sn}. Il résout successivement les sous-problèmes suivants :

𝒲ijk est le poids minimal d'un chemin du sommet si∈S au sommet sj∈Sn'empruntant que des sommets intermédiaires dans {s1,s2,…,sk}∈S s'il en existe un, et ∞ sinon.

On note 𝒲k la matrice des 𝒲ijk. Pour k=0, 𝒲0 est la matrice d'adjacence définissant G. Maintenant, pour trouver une relation de récurrence, on considère un chemin p entre si et sj de poids minimal dont les sommets intermédiaires sont dans {s1,s2,…,sk}. De deux choses l'une :

L'observation ci-dessus donne la relation de récurrence 𝒲ijk=min⁡(𝒲ijk−1,𝒲ikk−1+𝒲kjk−1), pour tous i, j et k dans {1,2,…,n}. Ainsi on résout les sous-problèmes par valeur de k croissante.

Pseudo-code

Donnons d'abord une première version d'après l'analyse faite dans la section précédente. Le pseudo-code suivant effectue ce calcul :

 fonction FloydWarshall (G)
   𝒲0:= matrice d'adjacence de G (matrice 𝑛×𝑛)
   for 𝑘:=1 to 𝑛
       for 𝑖:=1 to 𝑛
           for 𝑗:=1 to 𝑛
                𝒲ijk=min⁡(𝒲ijk−1,𝒲ikk−1+𝒲kjk−1)
   renvoyer 𝒲n

On peut optimiser l'algorithme en effectuant le calcul en place dans une unique matrice 𝒲. Le pseudo-code suivant effectue ce calcul :

 fonction FloydWarshall (G)
   𝒲:=matrice d'adjacence de G (matrice 𝑛×𝑛)
   for 𝑘:=1 to 𝑛
       for 𝑖:=1 to 𝑛
           for 𝑗:=1 to 𝑛
                𝒲𝑖𝑗:=min⁡(𝒲𝑖𝑗,𝒲𝑖𝑘+𝒲𝑘𝑗)
   renvoyer 𝒲

La complexité en temps, dans le pire cas, de cet algorithme (deuxième version) est O(n3) et sa complexité en espace O(n2).

Exemple

L'algorithme est exécuté sur le graphe à gauche.

Floyd-Warshall example

Applications

L'algorithme de Floyd-Warshall peut être utilisé dans les situations suivantes :

Améliorations

En 1993, Bahar et coll. ont donné une implémentation de l'algorithme de Floyd-Warshall pour des graphes représentés symboliquement à l'aide d'une structure de données appelée diagramme de décision algébriques qui est une généralisation des diagrammes de décision binaire.

Voir aussi