README.md 2 ko
Newer Older
ic194665's avatar
ic194665 a validé
## 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.
ic194665's avatar
ic194665 a validé

#### 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.
- Si **m** est tres grand djikstra de graph stream l'emportera largement.

Ici ma stratégie de test consiste à tester avec 3 degrés moyen différents tout
en variant le nombre de noeuds:

- **Test 1 **: degré moyen=3 :

![](/src/main/resources/averagedegre3/averagedegre3.png)