- Algorithme de warshall
-
Algorithme de Warshall
L'algorithme de Warshall permet de construire la fermeture transitive d'un graphe orienté ou non orienté.
Sommaire
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] 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 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é.
Catégorie : Algorithme de la théorie des graphes
Wikimedia Foundation. 2010.
