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) est un algorithme pour déterminer tous les plus courts chemins dans un graphe orienté et valué, en temps cubique.

Algorithme[modifier | modifier le code]

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 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 \mathcal{W}^k la matrice telle que \mathcal{W}^k_{ij} 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 sinon. \mathcal{W}^0 est la matrice définissant G. L'observation ci-dessus se traduit par l'égalité \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}, en supposant les opérations \min et + convenablement adaptées au cas d'un opérande ∞. Dès lors, on peut calculer successivement les matrices \mathcal{W}^k pour k=1, 2, 3, 4, …, n. Le calcul peut même être effectué en place, dans une unique matrice \mathcal{W}. Le pseudo-code suivant effectue ce calcul :

procedure FloydWarshall (G : matrice \mathit{n} \times \mathit{n})
\mathcal{W} := G
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}})

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

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.

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

Voir aussi[modifier | modifier le code]