Member 12876914 Ответов: 2

Ошибка сегментации алгоритма Дейкстры

Я создаю программу алгоритма Дейкстры, используя список смежности. Мой учитель дал мне эту структуру.

Где аргумент 'nom` - вершины,' poids` - вес, 'som_a' и 'som_b` - вершины,` nbsomets ` - количество вершин,` nbArcs ` - количество ребер,` NB_SOM_MAX' - максимальное количество вершин.

У меня нет ошибок компиляции, и когда я выполняю свою программу, у меня есть ошибка сегментации.

Что я уже пробовал:

//list of couples (sommet,poids)
 typedef struct maillon{
     struct maillon *suiv;
     int nom;
     int poids;
 } MAILLON, *LISTE;


 //graph structure
 typedef struct graphe{
     int nbSommets;
     LISTE Adj[NB_SOM_MAX]; //liste d'adjacence
 } GRAPHE;


 //insert (som_b, poids) At the top of the adjacency list Adj[som_a]
 void insere(int som_a, int som_b, int poids, LISTE Adj[]){
     LISTE prem=malloc(sizeof(LISTE));
     prem->nom = som_b;
     prem->poids = poids;
     prem->suiv = Adj[som_a];
     Adj[som_a] = prem;
 }


 //Initialization of the adjacency table: all lists are empty
 void initAdjGraphe(GRAPHE *G){
     int i;
     for(i = 0; i < G->nbSommets; i++){
         G->Adj[i] = NULL;
     }
 }


 //Load a graph from a file
 void litGraphe(char *adr, GRAPHE *G){
     FILE *f;
     int sa,sb,pds,nbArcs;
     f=fopen(adr,"r");
     fscanf(f,"%d",&(G->nbSommets));
     initAdjGraphe(G);
     fscanf(f,"%d",&nbArcs);
     while(nbArcs){
         fscanf(f,"%d %d %d",&sa,&sb,&pds);
         insere(sa,sb,pds, G->Adj);
         nbArcs--;
     }
     fclose(f);
 }



 //Displaying a graph
 void afficheGraphe(GRAPHE G){
     int j;
     printf("%d\n", G.nbSommets);
     for(j = 0; j < G.nbSommets; j++){
         while(G.Adj[j]->suiv != NULL){
             printf("%d %d %d\n",j, G.Adj[j]->nom, G.Adj[j]->poids);
             G.Adj[j] = G.Adj[j]->suiv;
         }
     }
 }

 //Dijkstra algorithm: displays the shortest path between s and all vertices of G
 void dijsktra(int s, GRAPHE G){
     int i,j,dist[NB_SOM_MAX], INT_MAX, pred[NB_SOM_MAX], min, nb=0,nbmin=0;
     LISTE S,F = G.Adj;
     for(i = 0; i<g.nbsommets; i++){="" dist[i]="INT_MAX;" pred[i]="NULL;" }="" dist[0]="0;" s="NULL;" while(f="" !="NULL){" min="G.Adj[0]-">poids;
         for(i = 1; i<g.nbsommets; i++){="" if(min=""> G.Adj[i]->poids){
                 min = G.Adj[i]->poids;
                 nbmin = i;
             }
         }
         insere(nb, nbmin, min, &S);
         nb++;
         if(nbmin == 0){
             F = F->suiv;
         }
         else{ // F[nbmin-1]->suiv = F[nbmin+1];
             F[nbmin-1] = F[nbmin+1];
         }

         for(i = G.Adj[nbmin]->nom; i<g.nbsommets; i++){="" if(dist[i]=""> dist[nbmin] + G.Adj[nbmin]->poids){
                 dist[i] = dist[nbmin] + G.Adj[nbmin]->poids;
                 pred[i] = nbmin;
             }
         }
     }

     for(i = 0; i < G.nbSommets; i++){
         printf("Chemin optimal de %d à %d : ", i, s);
         printf("%d-", i);
         j=i;
         while(pred[j] != s || pred[j] != NULL){
             printf("%d-", pred[j]);
             j=pred[j];
         }
         printf("\n");
     }
 }



 int main(void){
     GRAPHE G;
     litGraphe("./graphe.txt", &G);
     afficheGraphe(G);
     dijsktra(0, G);
     return 0;
 }

2 Ответов

Рейтинг:
5

Jochen Arndt

Часто бывает трудно найти источники, просто прочитав код (я пробовал). Он может быть даже получен путем загрузки недопустимых значений из файла. Это выглядит подозрительно, потому что Вы читаете индекс из файла (значение первой дуговой линии). Когда это выходит за пределы диапазона или нет строк для всех индексов, ваш код будет аварийно завершаться позже (с отсутствующими индексами в вашей структуре будут пустые записи).

Поэтому я предлагаю добавить проверки для проверки правильности параметров и переменных.

Быстрый первый подход может быть использован утверждать - Справочник по c++ [^].

Некоторые примеры для вашего кода:

#include <assert.h>

void insere(int som_a, int som_b, int poids, LISTE Adj[]){
    assert(som_a >= 0 && som_a < NB_SOM_MAX);
    /* EDIT: Must be off course Adj
    assert(LISTE != 0);
    */
    assert(Adj != 0);

     LISTE prem=malloc(sizeof(LISTE));
     prem->nom = som_b;
     prem->poids = poids;
     prem->suiv = Adj[som_a];
     Adj[som_a] = prem;
}

void initAdjGraphe(GRAPHE *G){
    assert(G);
    assert(G->nbSommets < NB_SOM_MAX);
     int i;
     for(i = 0; i < G->nbSommets; i++){
         G->Adj[i] = NULL;
     }
 }

Для initAdjGraphe() было бы еще лучше установить все элементы в NULL.

Окончательная реализация вернет код ошибки и / или напечатает сообщение об ошибке:
int insere(int som_a, int som_b, int poids, LISTE Adj[]){
    if (som_a < 0 || som_a >= NB_SOM_MAX)
    {
        printf("som_a value %d is invalid\n", som_a);
        return -1;
    }
    /* EDIT: Again it  must be Adj
    if (LISTE == 0)
    */
    if (Adj == 0)
    {
        printf("Adj is NULL\n");
        return -1;
    }
    /* ... */
    return 0;
}

Рейтинг:
2

Patrice T

Вы должны научиться использовать отладчик как можно скорее. Вместо того чтобы гадать, что делает ваш код, пришло время увидеть, как он выполняется, и убедиться, что он делает то, что вы ожидаете.

Отладчик позволяет вам следить за выполнением строка за строкой, проверять переменные, и вы увидите, что есть точка, в которой он перестает делать то, что вы ожидаете.
Отладчик-Википедия, свободная энциклопедия[^]
Освоение отладки в Visual Studio 2010 - руководство для начинающих[^]

Отладчик здесь для того, чтобы показать вам, что делает ваш код, и ваша задача-сравнить его с тем, что он должен делать.
В отладчике нет никакой магии, он не находит ошибок, он просто помогает вам. Когда код не делает того, что ожидается, вы близки к ошибке.

[Французский]
1) Ton code n'est pas autonome, donc personne (ici) ne peut le compiler pour voir ce qui ce passe.

2)

Цитата:
У меня ошибка сегментации.
Калифорния veux остро дие Т программы essaie д'écrire à ООН будут обсуждены проблемы условий труда Квай Пе-луй-appartient пас. Soit tu écris après la fin d'un tableau, soit tu use un pointeur qui n'est pas initialisé.

3) Использовать Ле отладчик, ванная exécutant тонну программа à па-па, ту где проживают местонахождени я'endroit ну да Планте. Avec le debugger, tu pourras Inspector les variables pendant l'éxécution.