Newer
Older
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
TP3 - Plus courts chemin
==
Introduction
--
L'objectif du TP est d'implementer une version simple de l'algorithme de Dijkstra et de comparer les performances
obtenues avec la version de GraphStream sur différents graphes. On va d'abord voir le générateur, ensuite on étudiera
ma version de Dijkstra puis la version de GraphStream. Enfin on regardera les performances avec les tests.
Description du générateur
--
J'utilise un générateur de graphe aléatoire. Il fonctionne de la façon suivante :Dans le constructeur, on défini le
nombre de voisins moyens pour chaque sommet. Ensuite on fait une boucle qui va rajouter des sommets avec des arêtes aléatoires
parfois en rajoutant des sommets pour garder le nombre de voisins moyen correct.
Description de l'algorithme MyDijkstra
--
Pour l'implémentation de Dijkstra, j'ai repris l'algorithme vu en cours. Le principe est que l'on part d'un point et on
initialise un tableau avec la distance entre le sommet de départ et chaque autres sommets à l'infini. Après pour chaque
voisin du départ on met à jour la distance en prenant la plus petite. On passe ensuite au voisin (non traité) le plus proche
et ainsi de suite. À la fin, le tableau contient la distance la plus petite pour chaque sommet.
Dans le programme, j'utilise une hashmap pour associé les sommets à leur distance et une liste pour sauvegarder les sommets
déjà traités. La fonction argmin permet d'obtenir le sommet le plus "proche" parmi les sommets non traités. La node u est le sommet
qui est en cours de traitement, s’il n'y a plus de sommets à traiter car tous les sommets qui sont relié au sommet de départ
on était traité le programme s'arrête.
Pour utiliser ma version de dijkstra, il faut fournir le graphe ainsi que le sommet de départ et on récupère la hashmap.
Comme pour chaque sommet on vérifie les voisins, mon algorithme a une complexité de O(n*m) avec n le nombre de noeuds et m le nombre d'arêtes.
Description de l'algorithme Dijkstra
--
L'algorithme de Dijkstra par GraphStream utilise le principe de "Tas de Fibonacci". Le tas de Fibonacci fonctionne avec un principe d'arbre.
Il fonctionne de manière paresseuse c'est-à-dire que certaine opérations sont effectué uniquement au moment on l'on a directement besoins du résultat.
Cela permet d'économiser certaines opérations qui ne seront jamais utilisées. L'algorithme utilisé par GraphStream a une complexité de O ( n log (n) + m )
avec n le nombre de noeuds et m le nombre d'arêtes.
- Pour commencer on définit une instance de Dijkstra avec les paramètres nécessaires.
- On initialise l'algorithme avec un graphe à travers init(graph)
- On calcule le chemin le plus court avec compute()
- Et on récupère les chemins les plus courts.
Description des tests
--
Voici les résultats des tests pour différents graphes:
Pour un générateur avec 5011 sommets et une moyen de 10 voisins.
|n°|Graphstream(en ms)|Personnel(en ms)
--|:-----:|---------------------:|
1|68|16561
2|86|14200
3|74|21470
4|77|18867
5|69|21208
6|80|16463
7|65|15399
8|54|16425
9|68|21418
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
Pour un générateur avec 1011 sommets et une moyen de 10 voisins.
|n°|Graphstream(en ms)|Personnel(en ms)
--|:-----:|---------------------:|
1|21|200
2|19|213
3|18|250
4|17|212
5|23|228
6|18|292
7|19|212
8|22|213
9|22|244
10|20|340
Pour un générateur avec 105 sommets et une moyen de 4 voisins
|n°|Graphstream(en ms)|Personnel(en ms)
--|:-----:|---------------------:|
1|5|7
2|7|6
3|7|9
4|6|10
5|7|7
6|6|6
7|7|7
8|7|7
9|5|6
10|6|7
Pour un générateur avec 1005 sommets et une moyen de 4 voisins.
|n°|Graphstream(en ms)|Personnel(en ms)
--|:-----:|---------------------:|
1|14|178
2|15|207
3|14|198
4|17|167
5|12|189
6|12|201
7|16|177
8|14|206
9|15|188
10|19|331
On remarque lors des tests que la complexité des algorithmes est respecté. Pour un nombre faible de sommets les algorithmes
sont un peu prés aussi efficace mais dès que le nombre de sommets augmente les faiblesses de mon algorithme sont alors misent en
évidence.
Conclusion
--
Pour conclure, ce TP m'a montré que programmer un algorithme naivement permet de comprendre le fonctionnement
mais n'est pas forcément le plus adapter pour des cas à grande échelle. Dans notre cas le principe de tas de Fibonacci fonctionne sur le meme
principe que mon algorithme mais il sauvegarde les données avec des arbres permettant de facilité les calculs. Offrant ainsi
des performance accrus.