BOURDIN PIERRICK M1 Informatique 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.