Re: [HS] Dijkstra en Gnu ?

[Alexandre Erisay <alexandre.erisay@bms.com>]

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 debian-user-french-request@lists.debian.org
> > with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
>
> --
> To UNSUBSCRIBE, email to debian-user-french-request@lists.debian.org
> with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org