Algorithme de Floyd-Warshall
1345341
31706655
2008-07-19T14:48:21Z
79.82.186.45
/* Algorithme */
En [[informatique]], l''''algorithme de Floyd-Warshall''' (parfois appelé '''algorithme de Roy-Floyd''' car décrit par [[Bernard Roy]] en 1959) est un [[Algorithmique|algorithme]] pour déterminer tous les [[problèmes de cheminement|plus courts chemins]] dans un [[théorie des graphes|graphe]] orienté et valué, en temps cubique.
==Algorithme==
L'algorithme de Floyd-Warshall prend en entrée un graphe orienté et valué (''V'', ''E''), sous la forme d'une [[matrice d'adjacence]]
donnant le poids d'un arc lorsqu'il existe et la valeur [[infini|∞]] 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 cycle de poids strictement négatif. L'algorithme calcule, pour chaque paire de sommets, le poids minimal parmi tous les chemins entre ces deux sommets.
Soit ''V'' = {1, 2, 3, 4, ..., ''n''} l'ensemble des sommets de ''G'' et soient ''i'' et ''j'' deux sommets de ''V''.
On considère un chemin ''p'' entre ''i'' et ''j'' de poids minimal dont les sommets intermédiaires sont dans {1, 2, 3, ..., ''k''}.
L'algorithme de Floyd-Warshall est basé sur l'observation suivante :
*soit ''p'' n'emprunte pas le sommet ''k'' ;
*soit ''p'' emprunte exactement une fois le sommet ''k'' (car les cycles sont de poids positifs ou nuls) et ''p'' est donc la concaténation de deux chemins, entre ''i'' et ''k'' et ''k'' et ''j'' respectivement, dont les sommets intermédiaires sont dans {1, 2, 3, ..., ''k''-1}.
Notons <math>\mathcal{W}^k</math> la matrice telle que <math>\mathcal{W}^k_{ij}</math> est le poids minimal d'un chemin de ''i'' à ''j'' n'empruntant que des sommets intermédiaires dans {1, 2, 3, ..., ''k''}, s'il en existe un, et [[infini|∞]] sinon. <math>\mathcal{W}^0</math> est la matrice définissant ''G''. L'observation ci-dessus se traduit par l'égalité
<math>\mathcal{W}^k_{ij} = \min(\mathcal{W}^{k-1}_{ij},\mathcal{W}^{k-1}_{ik}+\mathcal{W}^{k-1}_{kj})</math>, pour tous ''i'', ''j'' et ''k'' dans {1, 2, 3, 4, ..., ''n''}, en supposant les opérations <math>\min</math> et <math>+</math> convenablement adaptées au cas d'une opérande ∞. Dès lors, on peut calculer successivement les matrices <math>\mathcal{W}^k</math> pour ''k''=1, 2, 3, 4, ..., ''n''. Le calcul peut même être effectué en place, dans une unique matrice <math>\mathcal{W}</math>. Le pseudo-code suivant effectue ce calcul :
'''procedure''' ''FloydWarshall'' (<math>G</math> : matrice <math>\mathit{n} \times \mathit{n}</math>)
<math>\mathcal{W} := G</math>
'''for''' <math>\mathit{k} := 1</math> '''to''' <math>\mathit{n}</math>
'''for''' <math>\mathit{i} := 1</math> '''to''' <math>\mathit{n}</math>
'''for''' <math>\mathit{j} := 1</math> '''to''' <math>\mathit{n}</math>
<math>\mathcal{W}_{\mathit{i}\mathit{j}} := \min(\mathcal{W}_{\mathit{i}\mathit{j}}, \mathcal{W}_{\mathit{i}\mathit{k}} + \mathcal{W}_{\mathit{k}\mathit{j}})</math>
La complexité en temps de cet algorithme est O(n<sup>3</sup>) et sa complexité en espace O(n<sup>2</sup>).
==Applications==
L'algorithme de Floyd-Warshall peut être utilisé dans les situations suivantes :
* Plus courts chemins dans les graphes orientés (tous les arcs sont de poids 1)
* [[Clôture (mathématiques)|Clôture transitive]] d'un graphe orienté (algorithme de Warshall). Dans la formulation initiale de l'algorithme ci-dessus par Wharshall, 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 [[Algèbre de Boole (logique)|conjonction]] (ET) et le minimum par la [[Algèbre de Boole (logique)|disjonction]] (OU).
* Trouver une [[expression régulière]] dénotant le [[langage rationnel]] défini par un [[automate fini]]
==Références==
* {{en}} [[:en:Thomas H. Cormen|Thomas H. Cormen]], [[:en:Charles E. Leiserson|Charles E. Leiserson]], [[Ronald L. Rivest]], and [[:en:Clifford Stein|Clifford Stein]]. ''[[:en:Introduction to Algorithms|Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.
** Section 26.2, "The Floyd-Warshall algorithm", pp. 558–565;
** Section 26.4, "A general framework for solving path problems in directed graphs", pp. 570–576.
* {{en}} {{cite journal | first = Robert W. | last = Floyd | authorlink = Robert Floyd | title = Algorithm 97: Shortest Path | journal = [[:en:Communications of the ACM|Communications of the ACM]] | volume = 5 | issue = 6 | pages = 345 | date = June 1962 | id = {{doi|10.1145/367766.368168}} }}
* {{en}} {{cite journal | first = Stephen | last = Warshall | title = A theorem on Boolean matrices | journal = [[:en:Journal of the ACM|Journal of the ACM]] | volume = 9 | issue = 1 | pages = 11–12 | date = January 1962 | id = {{doi|10.1145/321105.321107}} }}
==Voir aussi==
* [[Robert Floyd]]
* [[Algorithme de Dijkstra]]
* [[Algorithme de Dantzig-Ford]]
{{Portail|informatique|logique}}
[[Catégorie:Algorithme de la théorie des graphes|Floyd-Warshall]]
[[cs:Floyd-Warshallův algoritmus]]
[[de:Algorithmus von Floyd und Warshall]]
[[en:Floyd–Warshall algorithm]]
[[es:Algoritmo de Floyd-Warshall]]
[[he:אלגוריתם פלויד-וורשאל]]
[[id:Algoritma Floyd-Warshall]]
[[it:Algoritmo di Floyd-Warshall]]
[[ja:ワーシャル-フロイド法]]
[[ko:플로이드-와셜 알고리즘]]
[[pl:Algorytm Floyda-Warshalla]]
[[pt:Algoritmo de Floyd-Warshall]]
[[sr:Флојд-Воршалов алгоритам]]
[[vi:Thuật toán Floyd]]
[[zh:Floyd-Warshall算法]]