Algorithme de Floyd-Warshall

Complexité en temps
Découvreur ou inventeur	Bernard Roy
Date de découverte	1959
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (en)
Structure des données	Graphe
Pire cas	O(\|S\|3)
Moyenne	O(\|S\|3)
Meilleur cas	O(\|S\|3)
Pire cas	O(\|S\|2)

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^[1] 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 = {s_{1}, s_{2}, \dots, s_{n}}$ . Il résout successivement les sous-problèmes suivants :

$𝒲_{i j}^{k}$ est le poids minimal d'un chemin du sommet $s_{i} \in S$ au sommet $s_{j} \in S$ n'empruntant que des sommets intermédiaires dans ${s_{1}, s_{2}, \dots, s_{k}} \in S$ s'il en existe un, et $\infty$ sinon.

On note $𝒲^{k}$ la matrice des $𝒲_{i j}^{k}$ . 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 $s_{i}$ et $s_{j}$ de poids minimal dont les sommets intermédiaires sont dans ${s_{1}, s_{2}, \dots, s_{k}}$ . De deux choses l'une :

soit $p$ n'emprunte pas le sommet $s_{k}$ ;
soit $p$ emprunte exactement une fois le sommet $s_{k}$ (car les circuits sont de poids positifs ou nuls) et $p$ est donc la concaténation de deux chemins, entre $s_{i}$ et $s_{k}$ et $s_{k}$ et $s_{j}$ respectivement, dont les sommets intermédiaires sont dans ${s_{1}, s_{2}, \dots, s_{k - 1}}$ .

L'observation ci-dessus donne la relation de récurrence $𝒲_{i j}^{k} = min (𝒲_{i j}^{k - 1}, 𝒲_{i k}^{k - 1} + 𝒲_{k j}^{k - 1})$ , pour tous $i$ , $j$ et $k$ dans ${1, 2, \dots, 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  $𝑛 \times 𝑛$ )
   for  $𝑘 := 1$  to  $𝑛$ 
       for  $𝑖 := 1$  to  $𝑛$ 
           for  $𝑗 := 1$  to  $𝑛$ 
                 $𝒲_{i j}^{k} = min (𝒲_{i j}^{k - 1}, 𝒲_{i k}^{k - 1} + 𝒲_{k j}^{k - 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  $𝑛 \times 𝑛$ )
   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 (n^{3})$ et sa complexité en espace $O (n^{2})$ .

Exemple

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

Pour $k = 0$ , les seuls chemins sont les arcs directs.
Pour $k = 1$ , on regarde les chemins où le sommet $s_{1}$ peut être un sommet intermédiaire. On trouve le chemin $s_{2} \to s_{1} \to s_{3}$ qui est moins lourd que $s_{2} \to s_{3}$ .
Pour $k = 2$ , maintenant, le sommet $s_{2}$ peut être un sommet intermédiaire. La boîte rouge et la boîte bleu montrent que le chemin $s_{4} \to s_{2} \to s_{1} \to s_{3}$ est la concaténation du chemin $s_{4} \to s_{2}$ et $s_{2} \to s_{1} \to s_{3}$ avec le sommet $s_{2}$ comme sommet intermédiaire. Notons que le chemin $s_{4} \to s_{2} \to s_{3}$ n'est pas considéré car c'est $s_{2} \to s_{1} \to s_{3}$ qui est un chemin le plus léger obtenu à l'itération précédente et non $s_{2} \to s_{3}$ .
Pour $k = 3$ , on trouve encore d'autres chemins.
Pour $k = 4$ , on a trouvé des plus courts chemins entre tous les sommets.

Applications

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

Plus courts chemins dans les graphes orientés non pondérés (en donnant un poids 1 à chaque arc)
Clôture transitive d'un graphe orienté (algorithme de Warshall). Dans la formulation initiale de l'algorithme ci-dessus par Warshall, le graphe n'est pas valué et donc simplement représenté par une matrice de booléens. On obtient alors la clôture transitive de ce graphe en remplaçant dans l'algorithme ci-dessus l'addition par la conjonction (ET) et le minimum par la disjonction (OU).
Trouver une expression régulière dénotant le langage rationnel défini par un automate fini. Les formules sont celles connues sous le nom d’algorithme de McNaughton et Yamada.

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^[2].

Notes et références

↑ Bernard Roy, « Transitivité et connexité. », C. R. Acad. Sci. Paris, vol. 249,‎ 1959, p. 216–218
↑ R. Iris Bahar, Erica A. Frohm, Charles M. Gaona et Gary D. Hachtel, « Algebraic decision diagrams and their applications », ICCAD '93 Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, IEEE Computer Society Press,‎ 7 novembre 1993, p. 188–191 (ISBN 0818644907, lire en ligne, consulté le 9 février 2018)

Références

(en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill, 2001, 2^e éd. [détail de l’édition]
- Section 26.2, "The Floyd-Warshall algorithm", p. 558–565;
- Section 26.4, "A general framework for solving path problems in directed graphs", p. 570–576.
(en) Robert W. Floyd, « Algorithm 97: Shortest Path », Communications of the ACM, vol. 5, n^o 6,‎ juin 1962, p. 345 (DOI 10.1145/367766.368168)
(en) Stephen Warshall, « A theorem on Boolean matrices », Journal of the ACM, vol. 9, n^o 1,‎ janvier 1962, p. 11–12 (DOI 10.1145/321105.321107)

Voir aussi

Portail de l'informatique théorique

[1] Bernard Roy, « Transitivité et connexité. », C. R. Acad. Sci. Paris, vol. 249,‎ 1959, p. 216–218

[2] R. Iris Bahar, Erica A. Frohm, Charles M. Gaona et Gary D. Hachtel, « Algebraic decision diagrams and their applications », ICCAD '93 Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, IEEE Computer Society Press,‎ 7 novembre 1993, p. 188–191 (ISBN 0818644907, lire en ligne, consulté le 9 février 2018)

[1]

[2]

v · m Algorithmes sur les graphes
Recherche	A* D* parcours en largeur parcours en largeur lexicographique parcours en profondeur recherche arborescente Monte-Carlo recherche best-first recherche en faisceau recherche jump point
Plus court chemin	Bellman-Ford Dijkstra Floyd-Warshall Johnson
Arbre couvrant minimum	Borůvka Kruskal Prim reverse-delete
Flot maximum	Dinic Edmonds-Karp Ford-Fulkerson Goldberg-Tarjan
Coupe minimum	Karger Stoer-Wagner
Composantes fortement connexes	Kosaraju Tarjan
Coloration	DSATUR Wigderson