Problème de segmentation
Audetee1216
Messages postés
1
Date d'inscription
Statut
Membre
Dernière intervention
-
[Dal] Messages postés 6205 Date d'inscription Statut Contributeur Dernière intervention -
[Dal] Messages postés 6205 Date d'inscription Statut Contributeur Dernière intervention -
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 !
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;
}
1 réponse
Bonjour,
En outre ta fonction de calcul de chemin devrait idéalement ne rien allouer. Elle devrait simplement prendre en paramètre :
Plusieurs conseils :
https://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.
En outre ta fonction de calcul de chemin devrait idéalement ne rien allouer. Elle devrait simplement prendre en paramètre :
- le graphe et les poids installés sur ses arcs, ou directement la matrice des poids
- le sommet source s
- le vecteur (pré-alloué) qui a chaque sommet t associe le poids du (d'un) plus court chemin de s à t
- le vecteur (pré-alloué) qui a chaque sommet t associe son (ou l'un de ses) prédécesseurs au sens des plus courts chemins de s à t
- Pour information, tu pourrais (comme boost) passer en paramètre l'algèbre de plus court chemin impliquée (dans ton cas (N, min, +) car les poids sont des entiers positifs, on prend les chemins de poids minimaux, et la longueur d'un chemin est obtenue en sommant les poids des arcs). En effet, les mathématiciens ont montré que l'algorithme de Dijkstra était valide dans tout semi anneau (par exemple ([0,1], max, x) ou (N, max, min)). Mais bon, pour le moment, oublions la généralisation de l'algorithme de Dijkstra et tenons-nous en à sa version de base.
Plusieurs conseils :
- Tant que tu débogues, hardcode le contenu de ta matrice, et commente la partie où tu saisis tout en attendant. En l'occurrence pour savoir comment déclencher ton erreur de segmentation, il faudrait nous dire quelle est ta matrice de poids, le sommet source, etc...
- Ça me paraît très compliqué comme implémentation. Voici le pseudo code que tu pourrais utiliser :
https://www.boost.org/doc/libs/1_41_0/libs/graph/doc/dijkstra_shortest_paths.html
- Indique avec des
printf
ce que l'utilisateur doit saisir (nombre de sommets, poids entre le sommet i et le sommet j, etc.) et les valeurs valides (valeurs positives, valeurs entre 0 et n, etc.) Idéalement contrôle la saisie, et utilise des poids qui garantissent que cette saisie est correcte (par exemple le nombre de sommet devrait être ununsigned int
ou unsize_t
). - Vérifie que pour chaque
malloc
, tu fais d'ici la fin du programme lefree
correspondant. Attention à les faire dans le bon ordre. Par exemple si tu désalloues ta matrice, il faut d'abord désallouer les lignes, et ensuite le tableau de lignes. - Essaye de localiser l'erreur de segmentation avec un débogueur (par exemple sous linux on utiliserait
gdb
), et le cas échéant en mettant desprintf
un peu partout dans ton code. - Aère ton code (espace autour des opérateurs =, ==, <=) et indente-le (accolades fermante sur une ligne vide et en dessous de la primitive correspondant).
Exemple :
for (i = 0; i < 10; ++i) {
printf("%d\n", i);
}
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.
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 :
https://www.valgrind.org/
https://openclassrooms.com/courses/debuguer-facilement-avec-valgrind
Dal