Newer
Older
## 1. Charger et afficher ce graphe. Appliquer une feuille de style pour rendre l'affichage plus joli et ressemblant à une carte routière. De quelle ville s'agit-il ?
## 2. Prendre quelques mesures de base de ce graphe : nombre de sommets et d'arêtes, degré moyen, distribution de degrés, coefficient de clustering. À votre avis, est-ce qu'on retrouve des valeurs similaires pour tout réseau routier ?
| Mesure | Résultat |
| :-------------------- | :------: |
| $`N`$ | 761 |
| $`E`$ | 1106 |
| $`\langle k \rangle`$ | 2.907 |
| $`\langle C \rangle`$ | 0.022 |
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
Pour ce qui est de retrouver des valeurs similaires sur tout autre réseau routier,
tout dépend de la taille du réseau routier et de son organisation. Sur des villes Européennes,
on aura de fortes chances d'avoir un degré moyen et un coefficient de clustering moyen similaire
mais si nous prenons des villes des Etats-Unis qui ont un aménagement très structurés en quadrillage,
le degré moyen devrait plus être aux alentours de 4.
## 3. (GPS) Toutes les arêtes possèdent un attribut "length" qui correspond à la longueur de l'arête en mètres. Faire une méthode permettant de trouver le plus court chemin entre deux sommets en utilisant l’algorithme de Dijkstra. Visualiser ce chemin en changeant la couleur des arêtes. Tester avec les sommets choisis au hasard.
Pour ce qui est de la méthode, ma solution consiste à passer deux paramètres
à la fonction de route, la source et la destination et de retourner le chemin complet.
```java
public Path route(Node a, Node b) {
Dijkstra dijkstra = new Dijkstra(Dijkstra.Element.EDGE, "result", "length");
dijkstra.init(graph);
dijkstra.setSource(a);
dijkstra.compute();
return dijkstra.getPath(b);
}
```
Voici le résultat obtenu en cliquant sur deux noeuds du graphe.
## 4. Pour les aventuriers qui se sentent à l'aise avec swing et qui veulent savoir plus sur le modèle événementiel de GraphStream, faire en sorte qu'on puisse choisir les sommets source et destination du plus court chemin en cliquant sur eux. S'inspirer de l'exemple donné ici.
Pour pouvoir avec le plus court chemin entre 2 noeuds depuis l'interface
graphique, il suffit de cliquer sur 2 noeuds à la suite.
Recliquer sur un noeud pour annuler l'action.
## 5. En se basant sur la complexité de ces deux algorithmes vus en cours, laquelle de deux approches ci-dessus sera plus efficace pour notre graphe ?
L'algorithme de Dijkstra est le plus adapté pour connaitre le chemin d'une
source vers l'ensemble des autres noeuds dans notre graphe car il est le plus
performant lorsqu'un graphe n'a que des arêtes positives.
De plus, Floyd-Warshall doit calculer l'ensemble des plus courts
chemin pour tous les noeuds du graphe avant de pouvoir récupérer le moindre résultat.
Pour le calcul du diamétre on a les compléxités suivants :
Floyd-Warshall : $`O(n^3) <=> 761^3 = 440711081`$
Dijkstra : $`O(n*(m+log(n))) <=> 761 * (1106 + log(761) = 843858`$
Théoritiquement, Dijkstra est 522 fois plus rapide.
## 7. Implémenter les deux approches, mesurer leur temps d'exécution. Est-ce que la réalité correspond à vos prévisions théoriques ?
| Algorithme | Temps (en seconde) |
| :------------- | :----------------: |
| Dijkstra | 1.8 |
| Floyd-Warshall | 45.5 |
Dans notre expérience, on peut constater que l'algorithme de Dijkstra
sera en moyenne 25 fois plus rapide que celui de Floyd-Warshall.
La réalité est donc bien inférieur aux prévisions théoriques.