Algorithme de Warshall
L'algorithme de Warshall, parfois appelé algorithme de Roy-Warshall est un algorithme agissant sur un graphe. Il permet de construire la fermeture transitive d'un graphe orienté ou non orienté, c'est-à-dire de construire un deuxième graphe sur le même ensemble de sommet, avec un arc d'un sommet u à un sommet v, si et seulement si il existe un chemin dans le graphe original de u à v. Cet algorithme donne donc des informations sur les composantes connexes ou fortement connexes d'un graphe.
Historique
[modifier | modifier le code]L'algorithme doit son nom à Stephen Warshall qui l'a publié en 1962[1], et il a été décrit également par Bernard Roy en 1959[2]. Robert W. Floyd[3] a publié dans les Communications of the ACM l'algorithme en quatre lignes (Algorithm 96) en même temps que son algorithme de calcul des plus courts chemins (Algorithm 97) connu sous le nom d'algorithme de Floyd-Warshall[4].
Principe
[modifier | modifier le code]À partir de la matrice d'adjacence C d'un graphe G, l'algorithme calcule la matrice d'adjacence C* de la fermeture transitive du graphe[5]. Les sommets du graphe sont numérotés de 1 à n.
L'algorithme calcule une suite de matrices Ck de matrices, pour k=0, etc.,n. La matrice C0 est la matrice C de départ, la matrice Cn est la matrice C* cherchée. Les matrices Ck vérifient la propriété que Ck[i,j]=1 s'il existe un chemin de i à j passant uniquement par des sommets inférieurs ou égaux à k, et 0 dans le cas contraire.
Cette propriété caractéristique est bien vérifiée pour k=0 et pour k=n. Pour construire la matrice Ck, on observe qu'il existe un chemin de i à j passant seulement par des sommets inférieurs ou égaux à k si et seulement s'il existe un chemin de i à j ne passant que par des sommets inférieurs ou égaux à k-1 ou alors s'il existe un chemin de i à k passant par des sommets inférieurs ou égaux à k-1 et un chemin de k à j passant par des sommets inférieurs ou égaux à k-1. Ce que l'on peut formuler par :
- .
![{\displaystyle C_{k}[i,j]=C_{k-1}[i,j]\lor (C_{k-1}[i,k]\land C_{k-1}[k,j])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/208efc9adbc0d5718587c9002bfcb32410ba52e5)
Ce principe est aussi utilisé dans l'algorithme de Floyd-Warshall.
Algorithme
[modifier | modifier le code]On peut écrire l'algorithme en pseudo-code comme suit (ici C est la matrice associée du graphe) :
Roy-Warshall (C)
C0 = C
pour k de 1 à n
pour i de 1 à n
pour j de 1 à n
Ck[i,j] = Ck-1[i,j] or (Ck-1[i,k] and Ck-1[k,j])
retourner Cn
On peut optimiser l'algorithme en effectuant le calcul en place dans une unique matrice C. Le pseudo-code suivant effectue ce calcul :
Roy-Warshall (C)
pour k de 1 à n
pour i de 1 à n
pour j de 1 à n
C[i,j] = C[i,j] or (C[i,k] and C[k,j])
retourner C
L'expression booléenne se réécrit avec des conditionnelles comme suit :
Roy-Warshall (C)
pour k de 1 à n
pour i de 1 à n
si C[i,k] alors
pour j de 1 à n
si C[k,j] alors C[i,j] = true
retourner C
Ceci est exactement la formulation de l'algorithme publiée dans les communications de l'ACM.
Exemple de fonction programmée en C qui, pour la matrice binaire d'adjacence C du graphe G donnée, calcule la matrice d'adjacence A de G*.
typedef _Bool MatAdj[n][n]; // où n est le nombre de sommets de G
void Warshall(MatAdj C, // la matrice d'adjacence de G
MatAdj A) // la matrice d'adjacence de G*
{
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é
[modifier | modifier le code]La construction de la fermeture transitive par l'algorithme de Warshall a une complexité en . Cela dit, il peut être intéressant de construire la fermeture transitive d'un graphe une fois pour toutes ; ainsi, on peut savoir par simple inspection si les sommets i et j appartiennent à la même composante connexe en un temps constant (réservé aux systèmes statiques).
Notes et références
[modifier | modifier le code]- (en) Stephen Warshall, « A theorem on Boolean matrices », Journal of the ACM, vol. 9, no 1, , p. 11–12 (DOI 10.1145/321105.321107)
- Bernard Roy, « Transitivité et connexité. », C. R. Acad. Sci. Paris, vol. 249, , p. 216–218.
- (en) Robert W. Floyd, « Algorithm 96: Ancestor », Communications of the ACM, vol. 5, no 6, , p. 344-345 (DOI 10.1145/367766.368168)
- Alexander Schrijver détaille les diverses contributions dans son livre : Combinatorial Optmization, Berlin, Springer, , 1881 p. (ISBN 978-3-540-44389-6, BNF 39117421), p. 129, Chapter 8 « Shortest paths : arbitrary lengths », Section 8.6g. Historical notes on shortest paths : All pairs : Roy, Warshall, Floyd, Dantzig.
- « Fermeture transitive : algorithme de Warshall », sur université du Québec à Montréal.
Voir aussi
[modifier | modifier le code]- Algorithmes de connexité basés sur des pointeurs (pour les graphes non orientés)
- Algorithme de Floyd-Warshall
- Problème de plus court chemin
- Fermeture transitive
