Posted June 11, 200322 yr J'en ai ras le bol, je jette l'éponge (temporairement) Y-a-t-il des programmeurs C en ligne?
June 11, 200322 yr Author 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é)
June 11, 200322 yr Author 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); }
June 11, 200322 yr Author 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...
June 11, 200322 yr Author Je crois que le code va partir en l'état chez le prof et :hellofuck: au prof qui est un tocard (et oui... les bons profs d'info, ils enseignent aux... infos, pas au chimi ) Je vai mettre trois pauvre commentaire... et hop
June 12, 200322 yr 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.
June 13, 200322 yr Author 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...
June 13, 200322 yr Author et t en koi pour faire c connerie laEcole d'ingénieur... ENSICAEN spécialité matériaux et chimie fine 1ère année.Le but est de nous faire maitriser le language C, et les questions de complexité et d'algorithmique
June 13, 200322 yr 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
June 13, 200322 yr Author 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
June 15, 200322 yr 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.
June 16, 200322 yr Author 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...
March 11, 200619 yr 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.
March 14, 200619 yr 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...
March 15, 200619 yr si le type cherche encore une réponse, il doit désespérer Si le type attendait la réponse, son uptime doit être interessant.
March 15, 200619 yr 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
March 15, 200619 yr En clair ce topic ne sert plus à rien, il est périmé. En conséquence je ferme (Note : Pas la peine de me vouvoyer )
Archived
This topic is now archived and is closed to further replies.