Warshall

Warshall est un algorithme qui réalise la fermeture transitive d'un graphe.

Il s'agit d'un algorithme présentant une complexité importante (de l'ordre de n³). On l'utilise donc avec des graphes statiques évoluant peu.

[modifier] Principe

La première boucle effecture une copie du graphe. Puis, on parcourt le graphe via une triple boucle en faisant varier 3 indices: i,j et k. S'il existe un arc de i vers k et de k vers j, alors il existe un chemin de i vers j. On ajoute donc un arc i -> j.

[modifier] Spécifications

Warshall prend en paramètre un graphe et renvoit un second graphe représentant la fermeture transitive de ce dernier.

[modifier] Implémentation

[modifier] C

t_graphe_s Warshall(t_graphe_s g)
{          
     t_graphe_s res;
     int i,j,k;
     

     res=init_graphe(g.ordre, g.estOriente);
     for(i=0;i<g.ordre;i++)
        for(j=0;j<g.ordre;j++)     
           *(res.adj+i*g.ordre+j) = *(g.adj+i*g.ordre+j);
           
     for(k=0;k<g.ordre;k++)
        for(i=0;i<g.ordre;i++)
           for(j=0;j<g.ordre;j++)
              if((*(g.adj+i*g.ordre+j)!=0.)||( (*(g.adj+i*g.ordre+k)!=0.) && (*(g.adj+k*g.ordre+j)!=0.)))
              {
                 printf("ajout du lien %d -> %d car chemin %d -> %d -> %d\n",i,j,i,k,j);
                 *(res.adj+i*g.ordre+j) = 1.;
              } else {
                 printf("pas d'ajout de lien %d -> %d car pas de chemin %d -> %d -> %d\n",i,j,i,k,j);
              }
              
     return res;
}