Algorithme de Warshall

Un article de Wikipédia, l'encyclopédie libre.

L'algorithme de Warshall permet de construire la fermeture transitive d'un graphe orienté ou non orienté.

Sommaire

[modifier] Principe

À partir de la matrice d'adjacence C du graphe G, on va calculer la matrice d'adjacence C* de G*.
On suppose que Ck[i,j] représente l'existence d'une chaîne de i à j passant uniquement par des sommets inférieurs ou égaux à k.
Il existe donc une chaîne de i à j passant seulement par des sommets inférieurs ou égaux à k s'il existe une chaîne de i à j passants seulement 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])

[modifier] 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]);
}

[modifier] 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 contruire la fermeture transitive d'un graphe une fois pour toute, 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).

[modifier] À voir également