## Graphe tp3 (djikstra) ### Introduction Le problème du plus court chemin est l'un des problèmes les plus répondu en théorie des graphes. Les algorithmes qui permettent de le résoudre sont nombreux, on s'intéresse ici au célèbre algorithme qui porte le nom de son inventeur (**DJIKSTRA**). **Remarque:** djikstra fonction que sur des poids positifs. ### 1.Le generateur utilisé **Random graph generator** a été utilisé pour créer les graphes, il crée un graphe aléatoire de taille (**taille**) et avec un degre moyen (**average degre**). ```java Graph graph2 = new SingleGraph("Random"); Generator gen = new RandomGenerator(averageDegre); gen.addSink(graph2); gen.begin(); for (int i = 0; i < taille; i++) gen.nextEvents(); gen.end(); ``` Lorsque **begin()** est appelée, il crée le premier nœud, puis un autre nœud est créé à chaque fois que **nextEvents()** est appelée, avec le degré moyen passé en paramètre bien sûr. #### 2. Mon algorithme Mon algorithme correspond à la version la plus naïve de djikstra: - Les éléments de ma liste **sont triés** donc : **O(1)** - add() : **O(n)** - Ce qui nous donne une complexité tolale de : **O(n × m)** ### 3.L'algorithme djikstra de graph stream D'aprés la documentation de graph stream, cet algorithme est très performant,sa complexité est : O (n log(n) + m). ### 4. Tests et résultats Avant de commencer les tests, faisant une comparaison entre les complexités des 2 algorithmes: - **n log(n) + m** et **n × m** On peut facilement remarquer que **n log(n) > n**, donc tout va se joueur avec le nombre de liens **m** de telle sorte que: - Si **m** est petit mon algorithme l'emportera (**n log(n) + m > n × m**). - Si **m** est tres grand djikstra de graph stream l'emportera largement (**n log(n) + m < n × m**). Ici ma stratégie de test consiste à tester avec 2 degrés moyen différents tout en variant le nombre de noeuds: - **Test 1 **: degré moyen=3 : ![](/src/main/resources/averagedegre3/averagedegre3.png) **Si m est très petit mon algorithme l'emportera** ==> :heavy_check_mark: :heavy_check_mark: - **Test 2 **: degré moyen=50 : ![](/src/main/resources/averagedegre50/averagedegre50.png) Le temps de mon algorithme augmente d'une manière phénoménale, tandis que le temps d'exécution de djikstra de graph stream **(courbe en violet presque sur la meme ligne avec y=0)** est presque insignifiant en le comparant à mon algorithme. Voici le [fichier contenant La courbe en violet ][identifier] (si on zoom les points ≠ (y=0)). **Si m est tres grand djikstra de graph stream l'emportera largement** ==> :heavy_check_mark: :heavy_check_mark: ### Conclusion Pour conclure, ce TP nous montre l'importance de la compléxité(l'optimisation) lorsqu'on travaille sur des cas qui nécessitent un nombre important de calculs. Un algorithme naïf permet de faire les taches demandées dans un intervalle de temps très. variant, ce temps dépend principalement du nombre de calculs contrairement à un algorithme optimisé qui garde un temps d'exécution presque stable malgré la grandeur des calculs. [identifier]: https://www-apps.univ-lehavre.fr/forge/ic194665/tp3-graph-djikstra_chaourar_imine/-/blob/master/src/main/resources/averagedegre50/djikstra(50)txt