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 C_k de matrices, pour k=0, etc.,n. La matrice C₀ est la matrice C de départ, la matrice C_n est la matrice C^* cherchée. Les matrices C_k vérifient la propriété que C_k[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 C_k, 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])}$.

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 ${\displaystyle \Theta (n^{3})}$. 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).