Click here to Skip to main content
15,887,676 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
I create a Dijkstra algorithm program using an adjacency list. My teacher give me this struct.

Where the argument `nom` is vertices, `poids` is weight, `som_a` and `som_b` are vertices, `nbSommets` is number of vertices, `nbArcs` is number of edges, `NB_SOM_MAX` is number of vertices MAX.

I don't have compilation errors and when I execute my program I have a segmentation fault.

What I have tried:

Objective-C
//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;
 }
Posted
Updated 29-Nov-16 22:29pm

You should learn to use the debugger as soon as possible. Rather than guessing what your code is doing, It is time to see your code executing and ensuring that it does what you expect.

The debugger allow you to follow the execution line by line, inspect variables and you will see that there is a point where it stop doing what you expect.
Debugger - Wikipedia, the free encyclopedia[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]

The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.

[Français]
1) Ton code n'est pas autonome, donc personne (ici) ne peut le compiler pour voir ce qui ce passe.

2)
Quote:
I have a segmentation fault.
Ca veux dire que ton programme essaie d'écrire à un endroit qui ne lui appartient pas. Soit tu écris après la fin d'un tableau, soit tu utilise un pointeur qui n'est pas initialisé.

3) Utilise le debugger, en exécutant ton programme pas à pas, tu pourra localiser l'endroit ou ça plante. Avec le debugger, tu pourras inspecter les variables pendant l'éxécution.
 
Share this answer
 
It is often difficult to find the sources by just reading the code (I tried it). It may be even sourced by loading invalid values from the file. This looks suspicious because you are reading the index from the file (first arc line value). When this out of range or there are not lines for all indexes, your code will crash later (with missing indexes there will be NULL entries in your struct).

So I suggest to add checks to verify that parameters and variables are valid.

A quick first approach might be using assert - C++ Reference[^].

Some examples for your code:
#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;
     }
 }

For initAdjGraphe() it would be even better to set all items to NULL.

A final implementation would return an error code and/or print an error message:
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;
}
 
Share this answer
 
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900