Aller au contenu

Besoin urgent d'aide en C (Ca peut sauver un TX)

Neo_13

Par Neo_13
dans Programmation et Lignes de code

Messages recommandés

Neo_13 Grand Maître

Neo_13

Posté(e)
  • Auteur
Posté(e)

Ca évolue dans le bon sens...

Mais je reviens dans 5min des fois que ça évolue plus correctement...

Extrait :

/*        TP Algorithme de  Moore-Dijkstra         */

/***************************************************/





#include <stdio.h>

#include <float.h>

#include <stdlib.h>



#define INFINI FLT_MAX



/********** Structure de donnees ******************************************/

typedef struct fils

{

int nom;

float longueur;

struct fils *suivant;

}Fils, *p_Fils;



typedef struct graphe 

{

 int n;

 p_Fils *table;

}Graphe;





/******** Fonction pour lire les donnees stockees dans un fichier texte ******/

Graphe lire_fichier(char * nom_fichier)

{

 int i;

 p_Fils p;

 FILE * fichier;

 int or, extr; /* pour une arete or--> sommet de depart   */

               /*              extr--> sommet d'arrivee   */             

 float longueur;  /* le cout entre or et extr */

 Graphe graphe;

 

   

 fichier = fopen(nom_fichier, "r");

 if (fichier == NULL)

   {

     printf("Fichier inexistantn");

     exit(1);

   }



 fscanf(fichier, "%d", &(graphe.n));

 graphe.table =(p_Fils *)malloc(graphe.n * sizeof(p_Fils));

 for(i = 0;i < graphe.n; ++i) graphe.table[i] = NULL;

 while (!feof(fichier))

   {

     p = (p_Fils) malloc(sizeof(struct fils));

     fscanf(fichier, "%d%d%f",∨, &extr, &longueur);

     p -> nom = extr;

     p -> longueur = longueur;

     p->suivant = graphe.table[or];

     graphe.table[or] = p; 

   }

 return graphe;

}





/**********Fonction d'affichage******************/

void affichage(Graphe graphe)

{

int i;

p_Fils p;

for(i=0;i<graphe.n;i++)

{

 printf("Sommet : %dn",i);

 p=graphe.table[i];

 while(p!=NULL)

 {

 	printf("%d t %.2ft",p->nom,p->longueur);

 	p=p->suivant;

 }

 printf("n");

}

}





/*********Fonction d'initialisation des tableaux**************/

void init(Graphe graphe,int r,int *ant, float *distance, int *appar)

{

int i;



for(i=0;i<graphe.n;i++)

{

 distance[i]=INFINI;

 appar[i]=0;

 ant[i]=-1;

}



distance[r]=0;

appar[r]=1;

ant[r]=-2;

}





/**********Fonction de calcul des distances******************/

void dijkstra(Graphe graphe, int r, int *ant, float *distance, int *appar)

{

int i;

int imin=8;

float min;

p_Fils p;





p=graphe.table[r];

while(p)

{

 if(distance[p->nom]>distance[r]+(p->longueur))

 {

 	distance[p->nom]=distance[r]+(p->longueur);

 	ant[p->nom]=r;

 }

 p=p->suivant;

}







}

void affich_tab(Graphe graphe,float *distance,int *ant)

{

int i;



for(i=0;i<graphe.n;i++)

{

 printf("%dt%.1ft%dn",i,distance[i],ant[i]);

}

}



int main(int argc, char ** argv)

{

int r;

int *ant;

int *appar;

float *distance;

Graphe graphe;



   if(argc <=2 || argc >=4) 

     {

       printf("nUsage: [graphe] [fichier_graphe.txt] [sommet de depart] n");

       exit(0);

     }

      /* int r;  r sommet de depart */

       r = atoi(argv[2]);



graphe = lire_fichier(argv[1]);

affichage(graphe);

   

ant=(int*)malloc(graphe.n*sizeof(int));

distance=(float *)malloc(graphe.n*sizeof(float));

appar=(int*)malloc(graphe.n*sizeof(int));



init(graphe,r,ant,distance,appar);

dijkstra(graphe,r,ant,distance,appar);



affich_tab(graphe,distance,ant);



return 0;

}

C'est la fonction dijkstra qui me pose problème (pas fini, paske à force de debugger, j'en ai eu marre, j'ai recommencé)

Lien vers le commentaire
Partager sur d’autres sites
Neo_13 Grand Maître

Neo_13

Posté(e)
  • Auteur
Posté(e)

Ben en fait le but c'est qu' a partir d'un graphe (représentant des villes et la distance entre elles), on puisse calculer la distance entre deux points...

La problème était la condition de fin de la récurrence...

Mais pour l'instant, ça a l'air de marcher

void dijkstra(Graphe graphe, int r, int *ant, float *distance, int *appar)

{

int i;

int imin=8;

float min=INFINI;

p_Fils p;





p=graphe.table[r];

while(p)

{

 if(distance[p->nom]>distance[r]+(p->longueur))

 {

 	distance[p->nom]=distance[r]+(p->longueur);

 	ant[p->nom]=r;

 }

 p=p->suivant;

}



for(i=0;i<graphe.n;i++)

{

 if(appar[i]==0 && ant[i]==r)

 {

 	if(distance[i]<min)

 	{

   min=distance[i];

   imin=i;

 	}

 }

}



p=graphe.table[r];

if(p)

dijkstra(graphe, imin, ant, distance, appar);



}

Lien vers le commentaire
Partager sur d’autres sites
Neo_13 Grand Maître

Neo_13

Posté(e)
  • Auteur
Posté(e)

Ah merde...

Ca marche pas comme ça devrait... (pas tout à fait...)

Tu connais l'algorithme de Moore-Dijkstra????

Paske là, mes viles sont telles que

0 1 5

0 2 20

0 3 40

1 2 10

1 4 7

1 5 20

2 3 10

2 5 10

4 5 10

4 7 40

6 5 20

7 5 10

Où le premier nombres est l'origine, le deuxième la destination et le 3e la longueur de l'arrête.

et par exemple ça ne me retourne pas de distance pour de 1 à 3...

Lien vers le commentaire
Partager sur d’autres sites
Neo_13 Grand Maître

Neo_13

Posté(e)
  • Auteur
Posté(e)
C'est pour quand ton projet ???

Tu devrais mettre des commentaires dans ton code, ça te permettrai de te relire et ça permet aux autre de te relire aussi.

cté pour mercredi (d'où l'urgent du titre)

Les commentaires, je les mets en général quand la fonction fonctionne.

merci à tous ceux qui aurait voulu m'aider.

Mon problème, c'est que le prof est un super tocard, et que je suis pas sûr qu'il comprenne lui même ce qu'il dit. Et il insiste pour qu'on utilise les mêmes structures que lui (dans mon code on voit 3 tableaus (dynamiques), moi, j'en aurai fait un seul à deux dimensions etc...

En plus tout ce semestre n'a été que tp à la con :

Représentation chainée de polynômes creux.

Arbre

Graphe de merde

Bref de la branlette intellectuel pour manipuler des trucs sur des sujets qui ne servent à rien. Un projet de programme plus complexe, mais avec un but aurait été plus intéressant je pense...

Lien vers le commentaire
Partager sur d’autres sites
Neo_13 Grand Maître

Neo_13

Posté(e)
  • Auteur
Posté(e)
oki ba dommage ke je connaise pa ton algo de Moore-Dijkstra car sa avai lair sympa comme prog c toujour mieu ke se ke g programmé tt lanné

tu pe me dire en kelke mot se ke c ke sa

A partir d'un graphe fléché représenté par le ficher txt 

0 1 5 

0 2 20 

0 3 40 

1 2 10 

1 4 7 

1 5 20 

2 3 10 

2 5 10 

4 5 10 

4 7 40 

6 5 20 

7 5 10

tu cherche quel est le distance à chaque point

en cherchant chaque fois le point le plus près, qui sert de pivot pour calculer la distance à ses fils etc...

le tablo dyn distance stocke la distance du point de départ à chacun de point

le tablo dyn ant stocke l'antécédent de chaque point

le tablo appar stocke si le point a déjà servi de pivot ou pas

Lien vers le commentaire
Partager sur d’autres sites
kjus Nouveau

kjus

Posté(e)
Posté(e)

Salut,

Je connais assez bien l'algorithme de Dijkstra.

Par contre ton implémentation me semble un peu obscure. Tu ne fais pas de tas pour garder les voies interessantes ?

Voila à peu près comment je fais :

tant que ! tas.empty()

position = depiler tas ;

si position est la position finale alors return position.distance;

ensuite on teste tous les chemins qui partent de position (ceux non deja empruntés), et on les empile sur le tas

et on met a jour un tableau temps_cumulé avec le temps pour aller vers chaque nouveau node.

fin tant

pour avoir la distance minimale pour aller de A vers B, on a juste a empiler la position A avec distance 0 au départ, et après l'algo de lire la case de temps_cumulé correspondant a la position B.

Lien vers le commentaire
Partager sur d’autres sites
Neo_13 Grand Maître

Neo_13

Posté(e)
  • Auteur
Posté(e)
Salut,

Je connais assez bien l'algorithme de Dijkstra.

Par contre ton implémentation me semble un peu obscure. Tu ne fais pas de tas pour garder les voies interessantes ?

Voila à peu près comment je fais :

tant que ! tas.empty()

position = depiler tas ;

si  position est la position finale alors return position.distance;

ensuite on teste tous les chemins qui partent de position (ceux non deja empruntés), et on les empile sur le tas

et on met a jour un tableau temps_cumulé avec le temps pour aller vers chaque nouveau node.

fin tant

pour avoir la distance minimale pour aller de A vers B, on a juste a empiler la position A avec distance 0 au départ, et après l'algo de lire la case de temps_cumulé correspondant a la position B.

Ben en fait, là il est pas vraiment fini... Mais j'en avais marre...

Disons que non, j'ai pas besoin de tas, j'utilise les tableaux pour ça... Mais il ne trace pas tout les itineraires...

Lien vers le commentaire
Partager sur d’autres sites
  • 2 ans après...
l_seringa Débutant

l_seringa

Posté(e)
Posté(e)

Ca évolue dans le bon sens...

Mais je reviens dans 5min des fois que ça évolue plus correctement...

Extrait :

/*        TP Algorithme de  Moore-Dijkstra         */

/***************************************************/





#include <stdio.h>

#include <float.h>

#include <stdlib.h>



#define INFINI FLT_MAX



/********** Structure de donnees ******************************************/

typedef struct fils

{

int nom;

float longueur;

struct fils *suivant;

}Fils, *p_Fils;



typedef struct graphe 

{

 int n;

 p_Fils *table;

}Graphe;





/******** Fonction pour lire les donnees stockees dans un fichier texte ******/

Graphe lire_fichier(char * nom_fichier)

{

 int i;

 p_Fils p;

 FILE * fichier;

 int or, extr; /* pour une arete or--> sommet de depart   */

               /*              extr--> sommet d'arrivee   */             

 float longueur;  /* le cout entre or et extr */

 Graphe graphe;

 

   

 fichier = fopen(nom_fichier, "r");

 if (fichier == NULL)

   {

     printf("Fichier inexistantn");

     exit(1);

   }



 fscanf(fichier, "%d", &(graphe.n));

 graphe.table =(p_Fils *)malloc(graphe.n * sizeof(p_Fils));

 for(i = 0;i < graphe.n; ++i) graphe.table[i] = NULL;

 while (!feof(fichier))

   {

     p = (p_Fils) malloc(sizeof(struct fils));

     fscanf(fichier, "%d%d%f",∨, &extr, &longueur);

     p -> nom = extr;

     p -> longueur = longueur;

     p->suivant = graphe.table[or];

     graphe.table[or] = p; 

   }

 return graphe;

}





/**********Fonction d'affichage******************/

void affichage(Graphe graphe)

{

int i;

p_Fils p;

for(i=0;i<graphe.n;i++)

{

 printf("Sommet : %dn",i);

 p=graphe.table[i];

 while(p!=NULL)

 {

 	printf("%d t %.2ft",p->nom,p->longueur);

 	p=p->suivant;

 }

 printf("n");

}

}





/*********Fonction d'initialisation des tableaux**************/

void init(Graphe graphe,int r,int *ant, float *distance, int *appar)

{

int i;



for(i=0;i<graphe.n;i++)

{

 distance[i]=INFINI;

 appar[i]=0;

 ant[i]=-1;

}



distance[r]=0;

appar[r]=1;

ant[r]=-2;

}





/**********Fonction de calcul des distances******************/

void dijkstra(Graphe graphe, int r, int *ant, float *distance, int *appar)

{

int i;

int imin=8;

float min;

p_Fils p;





p=graphe.table[r];

while(p)

{

 if(distance[p->nom]>distance[r]+(p->longueur))

 {

 	distance[p->nom]=distance[r]+(p->longueur);

 	ant[p->nom]=r;

 }

 p=p->suivant;

}







}

void affich_tab(Graphe graphe,float *distance,int *ant)

{

int i;



for(i=0;i<graphe.n;i++)

{

 printf("%dt%.1ft%dn",i,distance[i],ant[i]);

}

}



int main(int argc, char ** argv)

{

int r;

int *ant;

int *appar;

float *distance;

Graphe graphe;



   if(argc <=2 || argc >=4) 

     {

       printf("nUsage: [graphe] [fichier_graphe.txt] [sommet de depart] n");

       exit(0);

     }

      /* int r;  r sommet de depart */

       r = atoi(argv[2]);



graphe = lire_fichier(argv[1]);

affichage(graphe);

   

ant=(int*)malloc(graphe.n*sizeof(int));

distance=(float *)malloc(graphe.n*sizeof(float));

appar=(int*)malloc(graphe.n*sizeof(int));



init(graphe,r,ant,distance,appar);

dijkstra(graphe,r,ant,distance,appar);



affich_tab(graphe,distance,ant);



return 0;

}

C'est la fonction dijkstra qui me pose problème (pas fini, paske à force de debugger, j'en ai eu marre, j'ai recommencé)

slt vraiment j'ai lu ton programme alors ue moi ils me demande la meme chose mais avec des printf ,scanf..............alors puisque tu connais le'algorithme e moore et tu sait programmé en c alors si tu peut m'aider et ben merci d'avance.car j'en ai besoin de ca avant une semaine.

Lien vers le commentaire
Partager sur d’autres sites
l_seringa Débutant

l_seringa

Posté(e)
Posté(e)

Je parierais plutôt sur la fonction recherche du forum étant donné que notre ami a posté dans la section juste avant.

Ceci dit, vla le vieux up des chaumières... Faut pas s'attendre à grand chose de ce topic...

quoi j'ai pas compris ce que vous avez dit.merci

Lien vers le commentaire
Partager sur d’autres sites

Archivé

Ce sujet est désormais archivé et ne peut plus recevoir de nouvelles réponses.

Aller sur la liste des sujets
×
×
  • Créer...