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:
typedef struct maillon{
struct maillon *suiv;
int nom;
int poids;
} MAILLON, *LISTE;
typedef struct graphe{
int nbSommets;
LISTE Adj[NB_SOM_MAX];
} GRAPHE;
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;
}
void initAdjGraphe(GRAPHE *G){
int i;
for(i = 0; i < G->nbSommets; i++){
G->Adj[i] = NULL;
}
}
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);
}
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;
}
}
}
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] = 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;
}