Algorithme De Warshall

Algorithme de Warshall

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

Principe

À partir de la matrice d'adjacence C du graphe G, on va calculer la matrice d'adjacence C^* de G^*.
On suppose que C_k[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:

C_k[i,j]=C_k-1[i,j] OU (C_k-1[i,k] ET C_k-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 Θ(n³). 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).

À voir également

• Algorithmes de connexité.
• Les graphes.
• Théorie des graphes.
• Liste des algorithmes de la théorie des graphes algorithme de Warshall généralisé.

Ce document provient de « Algorithme de Warshall ».