Algo de Dijkstra en C : j'y arrive pas !!!!

Algo de Dijkstra en C : j'y arrive pas !!!! - C++ - Programmation

Marsh Posté le 19-04-2003 à 00:05:51    

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 :
  1. void Dijkstra ( GRAPHE *G , int depart , int *pere ) {
  3.   int *s_visite; /* BLANC si non visité, NOIR si visité */
  4.   int *d; /* correspond à l'estimation de la pondération du plus court chemin */
  5.   Liste l;
  6.   int i, n;
  7.   TAS tas;
  8.   ElementListe *u;
  9.    
  10.   /* Récupération du nb de sommets dans le graphe G */
  11.   n = G->nb_noeuds; 
  12.  
  13.   /* Initialisation des tableaux pour dijkstra */
  14.   s_visite = (int*) malloc ( n*sizeof (int) );
  15.   if ( s_visite == NULL ) {
  16.     fprintf(stderr,"\nErreur lors du malloc de l'initialisation du tableau s_visite !!\n" );
  17.     exit (1);
  18.   }
  19.  
  20.   d = (int*) malloc ( n*sizeof (int) );
  21.   if ( d == NULL ) {
  22.     fprintf(stderr,"\nErreur lors du malloc de l'initialisation du tableau d !!\n" );
  23.     exit (1);
  24.   }
  25.  
  26.   for ( i=0 ; i<n ; i++ ) {
  27.     d[i] = 100000;  /* 100000 pour dire l'infini */
  28.     pere[i] = -1;   /* Pour dire qu'aucun noeuds n'a de pere au début !! */
  29.     s_visite[i] = BLANC; /* Pour dire qu'aucun sommets n'est déjà visité */
  30.   }
  31.  
  32.   s_visite[depart] = NOIR;
  33.   d[depart] = 0; /* Fin initialisation */
  34.  
  35.   /* Creer le tas !!!! */
  36.   Creer_TAS ( &tas , n );
  37.  
  38.   /* Mettre ds le tas tous les sommets du graphe */
  40. /* ----> ON fait comment là ??? <------ */
  42.  
  43.   /* Recherche du chemin le plus court avec l'algo de Dijkstra */
  44.   while ( tas.nb_elt != 0 ) {
  45.  
  46.     u = Extraire_Min_TAS ( &tas );
  47.    
  48.     s_visite[u->valeur] = NOIR;
  49.    
  50.     l = G->tla[u->valeur]; /* recup le 1er elementliste sur lequel pointe u */
  51.    
  52.       while ( !EstVide ( l ) ) { /* Tant qu'il y a des sommets adjacents à u */
  53.      
  54.         Relacher ( u , l , pere , d );
  55.        
  56.         l = Reste ( l );
  57.        
  58.       }
  59.      
  60.   }
  61.  
  62. }
  63. int Relacher ( int u , Liste l , int *pere , int * d ) {
  65.   int w, v;
  66.  
  67.   v = l->valeur;
  68.  
  69.   w = l->poids;
  70.  
  71.   if ( d[v]>d[u]+w ) {
  72.  
  73.     d[v] = d[u] + w;
  74.    
  75.     pere[v] = u;
  76.    
  77.   }
  78.  
  79. }

 
ma strucutre de tas :
 

Code :
  1. struct s_tas {
  2.   ElementListe **tab; /* Un tableau de pointeurs sur des ElementListe */
  3.   int nb_elt;         /* nb d'elt à prendre en compte dans le tas */
  4.   int taille;         /* nb total d'elt du tas (le max) */
  5. };
  7. typedef struct s_tas TAS;


 
et ce qui faut pour comprende le tas :
 

Code :
  1. enum { BLANC, GRIS, NOIR }; /* Pour marquer les sommets */
  3. struct elementliste {
  4.   int valeur; /* Evident !! */
  5.   int poids; /* Poids sur l'arète */
  6.   struct elementliste *suivant; /* Pointeur sur un elementliste */
  7.                                 /* désignant l'elt suivant      */
  8. };
  10. typedef struct elementliste ElementListe, *Liste;
  12. typedef Liste *TLA;
  14. /* La structure pour le Graphe */
  15. struct s_graphe {
  16.   TLA tla; /* le tla */
  17.   int nb_noeuds;  /* le nb de noeuds du graphe */
  18.                   /* aussi appelés sommets     */
  19.   int nb_aretes;  /* le nb d'aretes du graphe  */
  20. };
  22. 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

Reply

Marsh Posté le 19-04-2003 à 00:05:51   

Reply

Marsh Posté le 19-04-2003 à 00:11:12    

mal a la tete

Reply

Marsh Posté le 19-04-2003 à 01:42:17    

Dijkstra, c'est bien un algo de cheminement dans les graphs non ?
 
T'ain c loin mes cours de maths :sweat:

Reply

Marsh Posté le 19-04-2003 à 07:48:00    

MagicBuzz a écrit :

Dijkstra, c'est bien un algo de cheminement dans les graphs non ?
 
T'ain c loin mes cours de maths :sweat:


 
plus court chemin (et encore je suis pas sûr alors que ca fait qu'un an :/)

Reply

Marsh Posté le 19-04-2003 à 10:36:50    

Oui c'est ca : le plus chemin d'un point a un autre ds un graphe !!
 
Des idées ?

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed