Algorithme de Floyd-Warshall

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique, l'algorithme de Floyd-Warshall (parfois appelé algorithme de Roy-Floyd car décrit par Bernard Roy en 1959[1]) 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 en le nombre de sommets.

Algorithme[modifier | modifier le code]

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. On suppose que les sommets de G sont {1, 2, 3, 4, …, n}. Il résout successivement les sous-problèmes suivants :

\mathcal{W}^k_{ij} est le poids minimal d'un chemin du sommet i au sommet j n'empruntant que des sommets intermédiaires dans {1, 2, 3, …, k} s'il en existe un, et sinon.

On note \mathcal{W}^k la matrice des \mathcal{W}^k_{ij}. Pour k = 0, \mathcal{W}^0 est la matrice d'adjacence définissant G. Maintenant, pour trouver une relation de récurrence, on considère un chemin p entre i et j de poids minimal dont les sommets intermédiaires sont dans {1, 2, 3, …, k}. De deux choses l'une :

  • soit p n'emprunte pas le sommet k ;
  • soit p emprunte exactement une fois le sommet k (car les circuits 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}.

L'observation ci-dessus donne la relation de récurrence \mathcal{W}^k_{ij} = \min(\mathcal{W}^{k-1}_{ij},\mathcal{W}^{k-1}_{ik}+\mathcal{W}^{k-1}_{kj}), pour tous i, j et k dans {1, 2, 3, 4…, n}. Ainsi on résout les sous-problèmes par valeur de k croissante.

Pseudo-code[modifier | modifier le 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)
    \mathcal{W}^0 := matrice d'adjacence de G (matrice \mathit{n} \times \mathit{n})
   for \mathit{k} := 1 to \mathit{n}
       for \mathit{i} := 1 to \mathit{n}
           for \mathit{j} := 1 to \mathit{n}
                \mathcal{W}^k_{ij} = \min(\mathcal{W}^{k-1}_{ij},\mathcal{W}^{k-1}_{ik}+\mathcal{W}^{k-1}_{kj})
   retourner \mathcal{W}^n            

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

 fonction FloydWarshall (G)
   \mathcal{W} :=matrice d'adjacence de G (matrice \mathit{n} \times \mathit{n})
   for \mathit{k} := 1 to \mathit{n}
       for \mathit{i} := 1 to \mathit{n}
           for \mathit{j} := 1 to \mathit{n}
                \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}})
   retourner \mathcal{W}

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

Exemple[modifier | modifier le code]

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

Floyd-Warshall example

  • Pour k=0, les seuls chemins sont les arcs directs.
  • Pour k=1, on regarde les chemins où le sommet 1 peut être un sommet intermédiaire. On trouve le chemin 2→1→3 qui moins lourd que 2→3.
  • Pour k=2, maintenant, le sommet 2 peut être un sommet intermédiaire. La boîte rouge et la boîte bleu montre que le chemin 4→2→1→3 est la concaténation du chemin 4→2 et 2→1→3 avec le sommet 2 comme sommet intermédiare. Notons que le chemin 4→2→3 n'est pas considéré car c'est 2→1→3 qui un chemin le plus léger obtenu à l'itération précédente et non 2→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[modifier | modifier le code]

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.

Notes et références[modifier | modifier le code]

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

Références[modifier | modifier le code]

Voir aussi[modifier | modifier le code]