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

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

À 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 :

.

Ce principe est aussi utilisé dans l'algorithme de Floyd-Warshall.

Algorithme

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é

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
  1. (en) Stephen Warshall, « A theorem on Boolean matrices », Journal of the ACM, vol. 9, no 1,‎ , p. 11–12 (DOI 10.1145/321105.321107)
  2. Bernard Roy, « Transitivité et connexité. », C. R. Acad. Sci. Paris, vol. 249,‎ , p. 216–218.
  3. (en) Robert W. Floyd, « Algorithm 96: Ancestor », Communications of the ACM, vol. 5, no 6,‎ , p. 344-345 (DOI 10.1145/367766.368168)
  4. 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.
  5. « Fermeture transitive : algorithme de Warshall », sur université du Québec à Montréal.

Voir aussi
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.