Newer
Older
1
2
3
4
5
6
7
8
9
10
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# TP3-Plus-Courts-Chemins Yacine Belmokhtar
## Introduction
Dans ce TP nous devons implémenter l'algorithme de Dijkstra de façon naïve sur un graphe généré aléatoirement. Ensuite comparer l'algorithme implémenté et l'algorithme présent dans GraphStream.
## Génération de graphe
Pour générer les différents graphes, j'ai utilisé `RandomGenerator` de GraphStream qui me permet de créer des graphes de tailles différentes.
``Generator gen = new RandomGenerator(degreMoyen, false, true);``
Le constructeur prend en paramètre:
- un double qui contient le degré moyen du graphe
- true si on veut qu'à chaque étape l'algorithme retire
- true si l'on veut que le graphe soit orienté, false si l'on veut que le graphe ne soit pas orienté
```java
Graph g = new SingleGraph("Graphe aléatoire");
g.setAttribute("ui.quality");
g.setAttribute("ui.antialias");
Generator gen = new RandomGenerator(degreMoyen,false, true);
gen.addSink(g);
gen.begin();
for(int i=0; i<nbSommet; i++)
gen.nextEvents();
gen.end();
```
## Dijkstra naïve
J'ai créé une classe `MonDijkstra` où se trouve une méthode `Dijkstra(Graph g)` qui permet de parcourir le graphe et de lui appliquer l'algorithme de Dijkstra.
Dans un premier temps j'ai crée des méthodes pour alléger la méthode `Dijkstra(Graph g)`. Ces méthodes sont:
- `getNodes(Graph g)` qui permet de me retourner une ArrayList de noeud présent dans le graphe
- `sommetMin(Node n)` qui me permet de récupérer le noeud minimum présent dans l'ArrayList
Tout d'abord, je récupère tout les noeuds du graphe dans une ArrayList en utilisant la méthode `getNodes(Graph g)`. Ensuite, je récupère le noeud minimum en utilisant la méthode `sommetMin(Node n)` et je boucle tant que le noeud n'est pas null.
Je retire le noeud actuelle de l'ArrayList. Je lui ajoute un attribut "marque" qui est à `true`.
Puis je boucle sur les voisins du noeud actuel. Je récupère la distance de l'arc, le poids du noeud actuel et le poids du voisin.
SI le poids du voisin est plus grand que l'addition entre la distance de l'arc et le poids du noeud actuel ET qu'il ne possède pas l'attribut "marque" ALORS je change le poids du voisin et lui ajoute un attribut "pere" qui contient le noeud qui permet de garder le chemin.
## Dijkstra de GraphStream
La classe Dijkstra de GraphStream permet de trouver le plus court chemin entre deux noeuds dans le graphe. Cette classe permet d'initialiser le noeud de départ``dijkstra.setSource(graphe.getNode(0));``.
Pour l'utiliser il faut lui donner le graphe que l'on veut utiliser ainsi que le noeud de départ.
Exemple:
```java
Dijkstra dijkstra = new Dijkstra(Dijkstra.Element.EDGE, null, "distance");
dijkstra.init(graphe);
dijkstra.setSource(graphe.getNode(0));
dijkstra.compute();
```
## Tests et Résultats
J'ai testé sur des graphes de taille: 10, 50, 100, 500, 1 000, 5 000, 10 000.
| Nombre de noeud | Degré Moyen |
|:-----------------------------|:------------|
| 10,50 | 9 |
| 100, 500, 1000, 5000 | 30 |
| 10 000 | 50 |
J'ai aussi calculé le temps d'exécution des deux algorithmes de Dijkstra pour savoir lequel des deux est le plus efficace.
``System.currentTimeMillis()`` qui me permet de récupérer le temps en millisecondes à un instant t.
Avec le graphe, nous pouvons remarquer que le temps d'exécution augmente avec le nombre de noeud.
En ce qui concerne la méthode naïve le temps d'exécution pour un petit nombre de noeud est équivalente à celle de GraphStream.
Par contre, dès lors qu'on passe à un nombre de noeud beaucoup plus élevé le temps d'exécution augmente drastiquement. Le temps d'exécution de Dijkstra naïve est exponentiel.