Algorithme de Warshall

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

Principe

À partir de la matrice d'adjacence C du graphe G, l'algorithme calcule la matrice d'adjacence C* de G*, la fermeture transitive de G.
On suppose que Ck[i,j] vaut 1 s'il existe une chaîne de i à j passant uniquement par des sommets inférieurs ou égaux à k, et 0 dans le cas contraire.
Il existe donc une chaîne de i à j passant seulement par des sommets inférieurs ou égaux à k si et seulement s'il existe une chaîne de i à j ne passant que par des sommets inférieurs ou égaux à k-1 ou alors s'il existe une chaîne de i à k passant par des sommets inférieurs ou égaux à k-1 ET une chaîne de k à j passant par des sommets inférieurs ou égaux à k-1. Ce que l'on peut résumer par:

Ck[i,j]=Ck-1[i,j] OU (Ck-1[i,k] ET Ck-1[k,j])

Algorithme

C est la matrice (booléenne) d'adjacence du graphe G et A est la matrice d'adjacence de G*.

typedef bool [n][n] MatAdj; /* où n est le nombre de sommets de G */

void Warshall(MatAdj C,
              MatAdj A)
{
int i, j, k;

for(i = 0; i < n; i++)
   for(j = 0; j < n; j++)
      A[i,j] = C[i,j];
for(k = 0; k < n; k++)
   for(i = 0; i < n; i++)
      for(j = 0; j < n; j++)
         A[i,j] = A[i,j] || (A[i,k] && A[k,j]);
}

Complexité

La construction de la fermeture transitive par l'algorithme de Warshall a une complexité en Θ(n3). Cela dit, il peut être intéressant de construire la fermeture transitive d'un graphe une fois pour toutes, ainsi, on peut savoir si les sommets i et j appartiennent à la même composante connexe en un temps constant (réservé aux systèmes statiques).

Voir aussi


Wikimedia Foundation. 2010.

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

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Algorithme De Warshall — L algorithme de Warshall permet de construire la fermeture transitive d un graphe orienté ou non orienté. Sommaire 1 Principe 2 Algorithme 3 Complexité 4 À voir également …   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é. Sommaire 1 Principe 2 Algorithme 3 Complexité 4 À voir également …   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. 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-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 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 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 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 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

Share the article and excerpts

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