Bonjour à tous.

Je suis en train de programmer un algorithme de Dijkstra dont le graphe est représenté par listes d'adjacence, et c'est avec ces listes que j'ai un problème.

Le programme devra à terme appliquer l'algorithme de Dijkstra sur des graphes différents à l'intérieur d'une boucle. C'est à dire qu'à chaque itération, on efface le graphe de l'itération précédente et on en crée un nouveau.

Seulement voilà, je ne sais pas pourquoi mais de temps en temps, au bout d'un nombre totalement aléatoire d'itérations, le programme plante lors de la désallocation d'une des listes.

Graphe.h :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
struct liste{
    int id;
    double poids;
    liste *suiv;
};
 
class Graphe{
    public:
        Graphe();
        Graphe(int t);
        ~Graphe();
        int taille;
        liste *Sommets;
        void afficherSommets();
        int ajouterArc(int source, int id, double p);
        liste *creerSommet(int s, double p);
};
Graphe.cpp :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
// Constructeur par défaut
Graphe::Graphe(){
    taille=0;
    Sommets = NULL;
}
 
// Constructeur par valeurs
Graphe::Graphe(int t){
    taille = t;
    Sommets = new liste[taille];
    for(int i=0; i<taille; i++){
        // -1 = pas de sommet
        Sommets[i].id = -1;
        Sommets[i].poids = -1;
        Sommets[i].suiv = NULL;
    }
}
 
// Destructeur
Graphe::~Graphe(){
    for(int i=0; i<taille; i++){
        liste *l;
        l = &Sommets[i];
        liste *tmp;
        while(l!=NULL){
            tmp = l->suiv;
            delete l; // <- C'est ici que ça semble coincer
            l = tmp;
        }
    }
    delete [] Sommets;
}
 
// Affichage de la liste des sommets
void Graphe::afficherSommets(){
    liste *l;
    cout << "________________________________" << endl;
    cout << "Liste des Sommets : taille = " << taille << endl;
    for(int i=0; i<taille; i++){
        l = &Sommets[i];
        cout << "Sommet " << i << " : " << endl;
        while(l!=NULL){
            cout << "\t [" << l->id << "] " << l->poids << endl;
            l = l->suiv;
        }
    }
    cout << "________________________________" << endl;
}
 
// Création d'un sommet
liste *Graphe::creerSommet(int s, double p){
    liste *r = new liste;
    r->id = s;
    r->poids = p;
    r->suiv = NULL;
    return r;
}
 
// Ajout d'un arc
int Graphe::ajouterArc(int source, int id, double p){
    // liste des sommets adjacents au sommet source
    liste *tmp = &Sommets[source];
    // Si la liste ne contient aucun sommet
    if(tmp->id==-1){
        // On ajoute le premier sommet
        Sommets[source].id = id;
        Sommets[source].poids = p;
        Sommets[source].suiv = NULL;
        return 0;
    }
    // Sinon
    else{
        // Si le sommet existe déjà
        if(tmp->id==id)
            // Sortie (erreur)
            return -1;
        // On ajoute le sommet à la suite de la liste
        while (tmp->suiv!=NULL){
            // Si le sommet existe déjà
            if(tmp->id==id){
                // Sortie (erreur)
                return -1;
            }
            tmp = tmp->suiv;
        }
        // Ajout de l'arc
        tmp->suiv = creerSommet(id, p);
        return 0;
    }
}
Le main boucle en allouant et désallouant un Graphe*. Et au bout d'un moment, une erreur survient.
Je vous donne un exemple avec un graphe généré aléatoirement :

Le graphe :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
Liste des Sommets : taille = 232
Sommet 0 : 
	 [118] 641.102
	 [214] 96.2249
(...)
Sommet 78 :
(...)
	 [25] 863.765
	 [166] 554.827
Sommet 79 : 
	 [60] 658.406
	 [226] 992.187
	 [214] 975.89
	 [73] 921.842
(...)
J'ai affiché les valeurs des éléments de la liste lors de la désallocation (dans le destructeur de Graphe ( sous la forme ( id | poids | suiv->id ) )

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
 
(...)
	(25 | 863.765 | 166)
	(166 | 554.827 | NULL)
[79]---------------------------------
	(60 | 658.406 | 226)
Et le programme plante lors de la désallocation du premier élément du sommet n°79.

D'une manière générale, le programme plante toujours lors de la désallocation du premier élément d'une des listes (mais pas nécessairement la première liste, c'est complètement aléatoire).
Les itérations allocation/désallocation peuvent se succéder plusieurs fois avant de planter.

A la limite, je préfèrerai que ça plante tout le temps, mais le fait que ce soit de manière totalement aléatoire que rend complètement chèvre !!!
J'espère que vous pourrez m'aider.
Merci d'avance.