Algorithme de Floyd-Warshall

Algorithme de Floyd-Warshall

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.

Sommaire

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 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 k: = 1 to n
    for i: = 1 to n
        for j: = 1 to 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

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

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Floyd-Warshall de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Algorithme De Floyd-Warshall — 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. Sommaire …   Wikipédia en Français

  • Algorithme de floyd-warshall — 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. Sommaire …   Wikipédia en Français

  • Algorithme de Floyd — Warshall 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 …   Wikipédia en Français

  • Algorithme de Floyd de détection de cycle — Algorithme du lièvre et de la tortue Pour les articles homonymes, voir Le Lièvre et la tortue. L algorithme de Floyd de détection de cycle, encore connu sous le nom d algorithme du lièvre et de la tortue, est un algorithme pour détecter les… …   Wikipédia en Français

  • Algorithme Du Lièvre Et De La Tortue — Pour les articles homonymes, voir Le Lièvre et la tortue. L algorithme de Floyd de détection de cycle, encore connu sous le nom d algorithme du lièvre et de la tortue, est un algorithme pour détecter les cycles dans des séquences arbitraires, qu… …   Wikipédia en Français

  • Algorithme du lievre et de la tortue — Algorithme du lièvre et de la tortue Pour les articles homonymes, voir Le Lièvre et la tortue. L algorithme de Floyd de détection de cycle, encore connu sous le nom d algorithme du lièvre et de la tortue, est un algorithme pour détecter les… …   Wikipédia en Français

  • Algorithme de Warshall — L algorithme de Warshall permet de construire la fermeture transitive d un graphe orienté ou non orienté. Il doit son nom à Stephen Warshall (en). Sommaire 1 Principe 2 Algorithme …   Wikipédia en Français

  • Algorithme du lièvre et de la tortue — Pour les articles homonymes, voir Le Lièvre et la Tortue. L algorithme de Floyd de détection de cycle, encore connu sous le nom d algorithme du lièvre et de la tortue, est un algorithme pour détecter les cycles dans des séquences arbitraires, qu… …   Wikipédia en Français

  • Floyd — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Floyd peut désigner : Sommaire 1 Patronyme 1.1 Noms composés …   Wikipédia en Français

  • Plus court chemin — Problèmes de cheminement Les problèmes de cheminement sont des problèmes classiques de la théorie des graphes. L objectif est de calculer une route entre des sommets d un graphe qui minimise ou maximise un certaine fonction économique. Le… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”