Problème de segmentation

Fermé

Audetee1216 Messages postés 1 Date d'inscription samedi 13 janvier 2018 Statut Membre Dernière intervention 13 janvier 2018 - Modifié le 13 janv. 2018 à 22:47
[Dal] Messages postés 6174 Date d'inscription mercredi 15 septembre 2004 Statut Contributeur Dernière intervention 2 février 2024 - 1 mars 2018 à 13:30

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;
}

A voir également:

Problème de segmentation
Erreur de segmentation - Forum C
Erreur de segmentation C++ ✓ - Forum C++
Erreur de segmentation (core dumped) ✓ - Forum C
Erreur de segmentation ✓ - Forum Linux / Unix
Le segment d'enregistrement de fichier est illisible - Forum Disque dur / SSD

1 réponse

Réponse 1 / 1

mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 7 749
Modifié le 28 févr. 2018 à 11:55

Bonjour,

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 un
```
unsigned int
```
ou un
```
size_t
```
).
Vérifie que pour chaque
```
malloc
```
, tu fais d'ici la fin du programme le
```
free
```
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 des
```
printf
```
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.

[Dal] Messages postés 6174 Date d'inscription mercredi 15 septembre 2004 Statut Contributeur Dernière intervention 2 février 2024 1 083
Modifié le 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 :

https://www.valgrind.org/
https://openclassrooms.com/courses/debuguer-facilement-avec-valgrind

Dal

Discussions similaires

Pb avec: Segmentation Fault (Core Dumped)

zsh: segmentation fault

Langage C - C/C++ Erreur de segmentation

Erreur de Segmentation (Core Dumped)

segmentation fault(core dumped ) avec gmp

Discussions similaires

Newsletters