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:
[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
- Algorithmes de connexité.
- Les graphes.
- Théorie des graphes.
- Liste des algorithmes de la théorie des graphes algorithme de Warshall généralisé.
