Bonsoir a vous, voila j'essaye de coder Dijkstra, mais je rencontre des difficultés...
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
 
/* Pour dijkstra */
typedef struct dijkstra
{
 int *Pred;
 int *Dist;
}Dijkstra;
 
/* Pour les matrices */
typedef struct mat
{
 int NbreLigne;
 int NbreColonne;
 int **Tableau;
} matrice, * PtrMatrice;
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
92
93
94
95
96
97
98
99
100
101
 
void AfficheTableau (int *tab, int taille);
 
int InitDijkstra (Dijkstra *resultat, int NbreSommet, int SommetInit);
 
/* On met a jour le tableau des distances et des prédécesseurs 
    On a initialisé le tableau des prédécesseur et des distances a -1, pour le
    tableau des distances la case du sommet initial contient 0
*/
void Relax (Dijkstra *dijk, int src, int dest, int val)
{
 if ((dijk->Dist[dest]==-1) || (dijk->Dist[src]+val < dijk->Dist[dest]))
   {
     if (dijk->Dist[dest]==-1)
      {
       dijk->Dist[dest] = val;
       dijk->Pred[dest] = src;   
      }
     else
      {
       dijk->Dist[dest] = dijk->Dist[src] + val;
       dijk->Pred[dest] = src;
      }
   }
}
 
/* Fonction qui retourne l'indice dans le tableau distance dont la valeur est minimal */
int RechercheMin (Dijkstra *dijk, int current, int nombre_sommet)
{
 int i, min=dijk->Dist[current], indice=0;
 for (i=0;i<nombre_sommet;i++)
   {
    if (dijk->Dist[i] != -1 && dijk->Dist[i]<dijk->Dist[current])
      {min = dijk->Dist[i]; indice++;}
   }
 return indice;
}
 
/* Pour tester si val est dans le tableau tab */
int Appartient (int *tab, int val, int nombre_sommet)
{
  int i;
  for (i=0;i<nombre_sommet;i++)
     if (tab[i]==val)
       return -2;
 return 1;
}
 
int AlgoDijkstra (Dijkstra *dijk, PtrMatrice StrucMatrice)
{
 int position_init = 0;
 int nbre_sommet;
 
 int i, min = 0;
 int current=0;
 int *ensemble;
 
 if (!(dijk)|| !(StrucMatrice)) {fprintf(stderr,"Erreur: les parametres passés a AlgoDijkstra sont NULL\n"); return FALSE;}
 
 /* Initialisation */ 
 nbre_sommet = StrucMatrice->NbreColonne;
 
 InitDijkstra (dijk, nbre_sommet, position_init);
 
 ensemble = calloc(nbre_sommet, sizeof(ensemble));
 if (!ensemble) {fprintf(stderr,"Erreur: Allocation memoire de ensemble dans AlgoDijkstra\n"); return FALSE;}
  for (i=0;i<nbre_sommet;i++)
    {ensemble[i] = -1;}
 
 int po = 0;
 /* Algo */
 while (current < nbre_sommet)
   {
 
    min = RechercheMin (dijk, po, nbre_sommet); 
    while (Appartient (ensemble,min, nbre_sommet) == -2)
         {po++;min = RechercheMin (dijk, po, nbre_sommet);}
    ensemble[current] = min;
    printf("Ensemble\t");AfficheTableau (ensemble, nbre_sommet);
    current++;
    for(i=0;i<nbre_sommet;i++)
      {
       if (StrucMatrice->Tableau[min][i]!=0)
          {Relax(dijk, min, i, StrucMatrice->Tableau[min][i]);
          printf("On affiche le tableau des distances\t");  AfficheTableau (dijk->Dist, nbre_sommet);}
      }
   }
 printf("On affiche le tableau des distances\n");
 AfficheTableau (dijk->Dist, nbre_sommet);
 return TRUE;
}
 
/* Teste si val est dans tab si oui renvoie -2 sinon 1 */
int Appartient (int *tab, int val, int nombre_sommet)
{
  int i;
  for (i=0;i<nombre_sommet;i++)
     if (tab[i]==val)
       return -2;
 return 1;
}
Mon ensemble contient aussi des sommets deja visité... alors qu'il ne doit contenir qu'une seule fois chaque sommet...
J'ai sûrement d'autres problèmes venant de ma fonction algo

Merci d'avance pour votre aide, car la je ne sais plus trop ou sont mes erreurs... Si vous pouviez me donner des pistes...