Bonjour,
je souhaite réaliser un programme pour trouver le plus court chemin avec un parcours en largeur, mais je ne parviens pas à trouver ce qui fait que lors des tests je trouve une erreur de segmentation.
Une piste ? Un conseil?
Merci bcp !
void Initial_parcours_largeur(int** matrix, int s, int t, int n){ int i; int** predecesseurs = (int**) malloc(n*sizeof(int*)); for(i = 0; i < n; i++) { int* ligne = (int*) malloc(n * sizeof(int)); predecesseurs[i] = ligne;} int** V = (int**) malloc(n*sizeof(int*)); for(i = 0; i < n; i++) { int* vi = (int*) malloc(n * sizeof(int)); V[i] = vi;} int* couleur = (int*) malloc (n * sizeof(int)); couleur[s]='N'; for(i=0 ; i<n ; i++){ couleur[i]='B';} int u=0; int c=1; int d=0; int b; if (s==t){ printf("%d\n",s+1); } else{ for (b=0; b<n; b++){ if (matrix[s][b]==1){ if(couleur[b]=='B'){ couleur[b]='N'; c++; V[d][u]=b; predecesseurs[d-1][u]=s; u++;}}} if (b==t){ printf("%d\n",s); printf("%d\n",t); } else{ d++; while (c!=n){ u=0; int m; int a; for (a=0;a<n;a++){ for (m=0;m<n;m++){ if (matrix[V[d-1][a]][m]==1){ if (couleur[m]=='B'){ couleur[m]='N'; c++; V[d][u]=m; predecesseurs[d-1][u]=V[d-1][a];}} if (b==t){ printf("%d\n",s); printf("%d\n",t); int* A = (int*) malloc (n*sizeof(int)); A[0]=predecesseurs[d-1][t]; int dep=d; int x=1; while (dep!=1){ A[x]=predecesseurs[dep][A[x-1]]; dep--; x++;} printf("%d\n",s); int z; for (z=d;z>0;z--){ printf("%d\n",A[z]);} } } } d++;}}} free(couleur); if (c>=n && n!=1){printf("not connected");} for(i = 0; i < n; i++) { free(predecesseurs[i]);} } int main() { int i,j; int n, s, t; scanf("%d",&n); int** matrix = (int**) malloc(n*sizeof(int*)); for(i = 0; i < n; i++) { int* line = (int*) malloc(n * sizeof(int)); matrix[i] = line; for(j = 0; j < n; j++) { scanf("%d", &line[j]); } } scanf("%d", &s); scanf("%d", &t); s--; t--; Initial_parcours_largeur(matrix,s,t,n); for(i = 0; i < n; i++) { free(matrix[i]); } free(matrix); return EXIT_SUCCESS; }
Marsh
NOVEMBER 9, 2013 AT 9:15 PM
Bonjour,
En outre ta fonction de calcul de chemin devrait idéalement ne rien allouer. Elle devrait simplement prendre en paramètre :
Plusieurs conseils :
http://www.boost.org/doc/libs/1_41_0/libs/graph/doc/dijkstra_shortest_paths.html
Exemple :
Ensuite il y a au moins une chose qui ne va pas dans ton programme. Si l'utilisateur saisit s=0 et/ou t=0, comme tu décrémentes s, tu peux arriver en dehors de matrix. Reply
réponses:
[Dal] on 1 mars 2018 à 13:30
par exemple sous linux on utiliserait gdb
Oui, gdb avec le core dump produit par l'erreur de segmentation et en utilisant les fonctionnalités de backtrace :
http://www.linux-france.org/article/devl/gdb_howto.html
Sous Linux, on dispose aussi du magnifique Valgrind, pour détecter les fuites mémoire et faire d'autres choses très sympas :
http://valgrind.org/
https://openclassrooms.com/courses/debuguer-facilement-avec-valgrind
Dal