Newer
Older
## 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.
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
#### 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 :
