Discussion :

[BatuBou]

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...

[FR119492]

Salut !

Implementation dijkstra en C
Bonsoir a vous, voila j'essaye de coder Dijkstra, mais je rencontre des difficultés...

Dijkstra en C
Bonsoir,
Je cherche a coder Dijkstra en C, j'ai donc regardé l'algo sur Wikipedia et j'aurais besoin d'explications dessus.

Est-il vraiment nécessaire d'ouvrir une seconde discussion sur le même sujet? Si vous êtesdans la même classe, collaborez!

Jean-Marc Blanc

[PRomu@ld]

Ce qu'il faut, c'est prendre fonction par fonction et tester si elles renvoient le résultat correct.

De plus, j'ai de légers doutes sur l'algorithme que tu utilises.

Plutôt que d'utiliser une valeur spéciale pour tes distances, initialise les distances à l'infini (FLT_MAX), ça évitera des cas spéciaux dans ta fonction de relâchement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
Relax( u , v , w )
SI d[v] > d[u] + w(u,v) alors 
     d[v]  <- d[u] + w(u,v) 
     pred(v) <- u
FIN SI

Pour ce qui est de l'algorithme, comme j'ai des doutes sur celui que tu utilises, sers-toi de ce pseudo code comme base :

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
 
-- G est le graphe, s est le sommet de départ.
-- w est la matrice de coût du graphe.
 
Dijkstra( G , s , w )
     Init(G,s)
     E <- Ensemble vide
     F <- tous les sommets de G
     TANT QUE F est non vide FAIRE
          u <- Extract( F )
          E <- Union( E , u )
          POUR tous les sommets v successeurs de u FAIRE 
               Relax(u,v,w)
          FIN POUR
     FIN TANT QUE

La fonction d'initialisation fixe une distance à l'infini pour tous les sommets sauf pour le sommet s où le coût vaut 0. Tous les prédécesseurs sont à null. E est l'ensemble des sommets déjà traités, F est une file à priorité (le premier sommet extrait est celui qui a la distance la plus faible).