- 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
Catégorie :- Algorithme de la théorie des graphes
Wikimedia Foundation. 2010.
