Miles--Teg | Salut,
voilà je dois faire en C l'algo de Dijkstra, avec une tri par tas (lequel est fait),
mais j'arrive pas à cerner l'algo et à le mettre en C !
Voilà ce que j'ai pour dijkstra :
Code :
- void Dijkstra ( GRAPHE *G , int depart , int *pere ) {
- int *s_visite; /* BLANC si non visité, NOIR si visité */
- int *d; /* correspond à l'estimation de la pondération du plus court chemin */
- Liste l;
- int i, n;
- TAS tas;
- ElementListe *u;
-
- /* Récupération du nb de sommets dans le graphe G */
- n = G->nb_noeuds;
-
- /* Initialisation des tableaux pour dijkstra */
- s_visite = (int*) malloc ( n*sizeof (int) );
- if ( s_visite == NULL ) {
- fprintf(stderr,"\nErreur lors du malloc de l'initialisation du tableau s_visite !!\n" );
- exit (1);
- }
-
- d = (int*) malloc ( n*sizeof (int) );
- if ( d == NULL ) {
- fprintf(stderr,"\nErreur lors du malloc de l'initialisation du tableau d !!\n" );
- exit (1);
- }
-
- for ( i=0 ; i<n ; i++ ) {
- d[i] = 100000; /* 100000 pour dire l'infini */
- pere[i] = -1; /* Pour dire qu'aucun noeuds n'a de pere au début !! */
- s_visite[i] = BLANC; /* Pour dire qu'aucun sommets n'est déjà visité */
- }
-
- s_visite[depart] = NOIR;
- d[depart] = 0; /* Fin initialisation */
-
- /* Creer le tas !!!! */
- Creer_TAS ( &tas , n );
-
- /* Mettre ds le tas tous les sommets du graphe */
- /* ----> ON fait comment là ??? <------ */
-
- /* Recherche du chemin le plus court avec l'algo de Dijkstra */
- while ( tas.nb_elt != 0 ) {
-
- u = Extraire_Min_TAS ( &tas );
-
- s_visite[u->valeur] = NOIR;
-
- l = G->tla[u->valeur]; /* recup le 1er elementliste sur lequel pointe u */
-
- while ( !EstVide ( l ) ) { /* Tant qu'il y a des sommets adjacents à u */
-
- Relacher ( u , l , pere , d );
-
- l = Reste ( l );
-
- }
-
- }
-
- }
- int Relacher ( int u , Liste l , int *pere , int * d ) {
- int w, v;
-
- v = l->valeur;
-
- w = l->poids;
-
- if ( d[v]>d[u]+w ) {
-
- d[v] = d[u] + w;
-
- pere[v] = u;
-
- }
-
- }
|
ma strucutre de tas :
Code :
- struct s_tas {
- ElementListe **tab; /* Un tableau de pointeurs sur des ElementListe */
- int nb_elt; /* nb d'elt à prendre en compte dans le tas */
- int taille; /* nb total d'elt du tas (le max) */
- };
- typedef struct s_tas TAS;
|
et ce qui faut pour comprende le tas :
Code :
- enum { BLANC, GRIS, NOIR }; /* Pour marquer les sommets */
- struct elementliste {
- int valeur; /* Evident !! */
- int poids; /* Poids sur l'arète */
- struct elementliste *suivant; /* Pointeur sur un elementliste */
- /* désignant l'elt suivant */
- };
- typedef struct elementliste ElementListe, *Liste;
- typedef Liste *TLA;
- /* La structure pour le Graphe */
- struct s_graphe {
- TLA tla; /* le tla */
- int nb_noeuds; /* le nb de noeuds du graphe */
- /* aussi appelés sommets */
- int nb_aretes; /* le nb d'aretes du graphe */
- };
- typedef struct s_graphe GRAPHE;
|
on considerera que les fonctions du tas son OK !! (si elles le sont pas, on verra plus tard ;o) !!)
Voilà, si quelqu'un qui avait fait cet algo en C pouvait me montrer ce qu'il a fait, ca m'aiderait beaucoup !!
Merci @+
Miles |
)