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