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
#### 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 :
**Si m est très petit mon algorithme l'emportera** ==> ✅ ✅.
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.
**Si m est tres grand djikstra de graph stream l'emportera largement* ==> ✅ ✅.
###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.