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
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
102
103
104
105
106
107
108
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:
|n°|essai|Graphstream Personnel
--|:-----:|---------------------:|
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
10|63|19504|
|n°|GrapheStream|Personnel|
|:-|:----------:|--------:|
|1|68|16561|
Pour commencer les tests auront un générateur avec un averageDegree à 10. MyDijkstra etant mon programme.
On commence les tests à 31 sommets, les résultats sont les suivants :
Dijkstra GraphStream
6 ms pour 31 sommet(s)
MyDijkstra
3 ms pour 31 sommet(s)
On peut voir que pour 31 sommets mon algorithme est plus rapide que celui de GraphStream.
On continue les tests avec 111 sommets, les résultats sont les suivants :
Dijkstra GraphStream Dijkstra GraphStream Dijkstra GraphStream
9 ms pour 111 sommet(s) 10 ms pour 111 sommet(s) 10 ms pour 111 sommet(s)
MyDijkstra MyDijkstra MyDijkstra
11 ms pour 111 sommet(s) 8 ms pour 111 sommet(s) 15 ms pour 111 sommet(s)
En effectuant plusieurs tests avec la même valeur la durée d'execution des deux algorithmes sont en moyennes équivalent, ils dépendent de la longueur du graph.
On continue les tests avec 5011 sommets, les résultats sont les suivants :
Dijkstra GraphStream Dijkstra GraphStream Dijkstra GraphStream
79 ms pour 5011 sommet(s) 107 ms pour 5011 sommet(s) 72 ms pour 5011 sommet(s)
MyDijkstra MyDijkstra MyDijkstra
29401 ms pour 5011 sommet(s) 30072 ms pour 5011 sommet(s) 12655 ms pour 5011 sommet(s)
On peut voir qu'avec un nombre bien plus grand de sommet la méthode de GraphStream devient beaucoup plus efficace. Le temps d'exécution reste plus ou moins le même pour GraphStream
alors que pour MyDijkstra le temps d'exécution devient énorme.
On continue les tests avec 15011 sommets, les résultats sont les suivants :
Dijkstra GraphStream
79 ms pour 15011 sommet(s)
MyDijkstra
424824 ms pour 15011 sommet(s)
C'est à ce moment là que la différence devient vraiment énorme, Dijkstra de GraphStream s'exécute en 79 ms alors que celui de MyDijkstra s'exécute en 424824 ms, ce qui correspond à plus de 7 minutes.