voila le code que j ai retrouve sur une disquette en gros j ai stocker dans un
AVL toute les permutation
pour acceder en 0(log(n!)) a une permutation donner et je commence l algo a la
permutation s. par contre
mon graphe est orienter donc je me suis permit des simplification de l algo de
dijkstra cette algo calcule
le plus court chemin pour aller de la permutation racine a un permutation
donner et stock son chemin dans l
avl. il calculer aussi la longueur du chemin. il fait en gros un parcour en
largeur.
il part de la racine "s" puis il affecte le chemin a tout les fils (valeur
ayant une arrete dans le graphe)
puis il traite tout les fils en ajoutant la valeur du fils.
ce qu il y a de compliquer dans le code c est qu on a stocker la liste des
valeur qui son lier avec a une
permutation et non pas une liste d'adresse. donc on a le faux (juste le nom)
puis on fait une recherche dans
l avl pour avoir l adresse et ontravail sur l adresse. j espere que ca t aidera
;).
void dijkstra(lpermut *avl,permut s)
{
int lg=0;
lpermut a=*avl;
lpermut bind,reelabind;
apermut abind;
/*initialisation*/
bind=recherche_permut(s,a);
bind->idway=malloc((int)sizeof(struct arete_permut));
bind->idway->p=copie_permut(s);
bind->lg=0;
/*tant que tout n est pas checker*/
/*remplir tout ceux qui on la meme lg */
abind=bind->la;/*on traite ces aretes */
while(abind)
{
reelabind=recherche_permut(abind->p,a);
if(reelabind->lg==-1)
{
reelabind->lg=lg+1;/*longueur de la permutation*/
reelabind->idway=change_chemin(bind->idway,reelabind->p);/*chemin vers s*/
}
abind=abind->next;
}
while(1)
{
bind=recherche_lg(a,lg);
if(bind==NULL) /*soit on a traiter tout ceux de meme longueur */
{ /*soit on les a tous checker */
lg++; /*on incremente pour verifier le premier cas */
bind=recherche_lg(a,lg);
if(bind==NULL) break; /*si il est toujours NULL alors c est
qu on a tous checker on a fini */
}
bind->checked=1;
abind=bind->la;/*on traite ces aretes */
while(abind)
{
reelabind=recherche_permut(abind->p,a);
if(reelabind->lg==-1)
{
reelabind->lg=lg+1;/*longueur de la permutation*/
reelabind->idway=change_chemin(bind->idway,reelabind->p);/*chemin vers s*/
}
abind=abind->next;
}
}
*avl=a;
}
void creer_chemin_id(lpermut *avl)
{
lpermut a=*avl;
permut s;
s=creer_permut(a->p->nb);
dijkstra(&a,s);
*avl=a;
}
Alexandre Erisay wrote:
> hmm j ai implementer l algo de Dijkstra en C pour le parcour d un graphe (
> graphe
> de permutation ) pour un projet d'iup.
> Si tu cherche des algos de trie il y a un tres bon bouquin algorithmique mais
> j
> ai plus la reference sur moi. je vais voir ce soir.
>
> Sinon il y a un cous de 2000/2001 de robert cori en ps un professeur de
> polytechnique ou il y a les implementation en C et pascal de pas mal d
> algo(arbre,quicksort,parcour en profondeure reequilibrge d arbre,.... )
>
> http://www.enseignement.polytechnique.fr/profs/informatique/Jean-Jacques.Levy/poly/polyx-cori-levy.ps.gz
>
> Olivier Garet wrote:
>
> > Bonjour,
> >
> > Pour ne pas réinventer la roue, je voudrais partir d'une implémentation
> > en C++ de l'algorithme de Dijkstra et l'adapter à mes besoins.
> > Problème: j'ai bien trouvé des programmes sur le net, mais pas sous licence
> > Gnu.
> > Où trouver ça ? De manière générale, existe-t-il des bibliothèques libres
> > bien organisées où trouver des implémentations d'algorithmes classiques ?
> >
> > Désolé pour le HS.
> >
> > A+
> >
> > Olivier
> >
> >
> > --
> > To UNSUBSCRIBE, email to [EMAIL PROTECTED]
> > with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
>
> --
> To UNSUBSCRIBE, email to [EMAIL PROTECTED]
> with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
