Dijkstra算法分割故障

问题描述

我使用邻接列表创建Dijkstra算法程序。我的老师给我这个结构。



参数`nom`是顶点，`poids`是重量，`som_a`和`som_b`是顶点，`nbSommets `是顶点数，`nbArcs`是边数，`NB_SOM_MAX`是顶点数MAX。



我没有编译错误，当我执行时我的程序我有分段错误。



我尝试过：

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:

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

推荐答案

引用：

我有分段错误。

Ca veux dire que ton program essaie d'écrireàunendroit qui ne lui appartient pas。 Soittuécrisaprèslafin d'un tableau，soit tu利用un pointeur qui n'stpasinitialisé。



3）利用le debugger，enexécutanttonprogram pas àpas，tu pourra localiser l'endroitouçaplatte。 Avec le debugger，tu pourras inspecter les variables pendant l'éxécution。

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.

#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 。



最终实现将返回错误代码和/或打印错误消息：

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

这篇关于Dijkstra算法分割故障的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！