## 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