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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
# TP3 - plus courts chemins
### De Molinier Hugo
#### Université Le Havre Normandie
Novembre 2025
---
## Introduction
Vous êtes un cycliste muni d'un vélo électrique et des cartes de quelques villes qui indiquent l'altitude de chaque intersections de la ville. Votre vélo électrique se décharge lors des montées et se recharge lors des descentes. Vous voulez calculer des itinéraires dans les villes dont vous avez les cartes en vue de vos prochaines vacances mais en minimisant la décharge de votre vélo.
On considère que s'il existe une route montante (ou plate) connectant l'intersection A et l'intersection B, le coût en électricité associé pour le vélo est 5\*(hauteur(B)-hauteur(A))+2 Wh et si la route descend alors le vélo se recharge de (hauteur(B)-hauteur(A))/2 Wh.
Chaque ville est représentée par un graphe orienté dont les sommets sont les intersections de rues et les arêtes sont les rues.
## Graphes représentant des villes
Ouvrez le fichier d'un des graphes fourni dans les ressources de ce TP.
- 1 Est-ce que les coûts des arêtes sont fournis ? Si non donnez la fonction qui prend en entrée une arête et renvoie le coût en dépense d’électricité de cette arête.
- 2 Est-ce que les coûts des arêtes peuvent être négatifs ? Est-ce que le graphe peut contenir des cycles de coût négatif ? En déduire l'algorithme adapté pour calculer le plus court chemin sur ces graphes.
### Application
Pour commencer avant tout, ils faut pouvoir faire une fonction pour ouvrir les fichiers .dgs . Donc on fait Graph getTheFileFromPath(String path)
- Pour la 1, non les coûts des arêtes sont fournis. Donc pour calculer le cout on fait une fonction pour une arretes données retournes qui fait ca :
```java
if (aHauteur<=bHauteur){//donc monte
return (5*(bHauteur-aHauteur)+2f);
}
return ((bHauteur-aHauteur)/2f);
```
- Pour savoir pour la 2 si il y a des cycles négatifs. On prend en compte que hauteur = 0.
Donc 5\*(0-0) +2 =2 (montée) et (0-0)/2 = 0 (déscente).
Donc montée + déscente = 2. Donc pas de cycle négatif.
L'algorithme le plus adapté pour un parcours de graph avec des couts d'arretes négatifs mais sans cycle est l'algorithme de Bellman-Ford.
Sur cette valeurs , on suppose que les fichiers graphes sont fait avec des valeurs réels ou réaliste. Hauteur (n mètre au dessus de la mer)
### Affichage
Pour la 1, par exemple l'arrete 5 de graphe_grenoble.dgs, retourne -4.0 :
```java
System.out.println(getCostOfTheArete(graph3.getEdge(5)));
```
## Algorithme de plus court chemin
Vous avez travaillé en cours sur des algorithmes de plus courts chemins.
- 1 En utilisant le cours, implémentez l'algorithme de plus court chemin que vous avez donné en réponse de la question 1.2.
- 2 Pensez à documenter et tester votre code. En bref, faites un travail propre.
### Application
1 : On a implémenter l'algorithme de bellmanFord qui renvoie 2 map. Fonction BellmanFord
Une map couts contenant le coût minimal pour atteindre chaque nœud u depuis la source s.
Une map pred indiquant le prédécesseur de chaque nœud sur le plus court chemin depuis la source.
On a aussi fait les améliorations possible (S'arrêter si pendant une itération il n'y a pas eu de mise à jour) qui change de 2s le temps d'executions pour graphe_lehavre.dgs par exemple
## Campagne de tests
Lorsqu'on implémente un nouvel algorithme, il est important de tester son efficacité.
- 1 Calculez le plus court chemin (au sens de la minimisation de l’électricité consommé) du sommet d'identifiant "33317746" au sommet d'identifiant "144477138" dans le graphe représentant la ville du Havre ("graphe_lehavre.dgs").Quel est le coût total en électricité de ce chemin ? Affichez ce chemin en modifiant certains paramètres d'affichages par défaut pour qu'il soit visible.
- 2 Il est évident qu'un seul exemple n'est pas représentatif. Pour chacun des graphes fournis, effectuez des tests sur l'algorithme.
- 3 On souhaite maintenant étudier la version de l'algorithme de Graphstream. Effectuez des tests sur cet algorithme.
### Application
1 : On a implémenter la possibilité d'optenir un chemin + son cout .
Le plus court chemin (au sens de la minimisation de l’électricité consommé) du sommet d'identifiant "33317746" au sommet d'identifiant "144477138" dans le graphe représentant la ville du Havre ("graphe_lehavre.dgs") est
:[33317746, 33294633, 11250583245, 11250583244, 33294670, 33317737, 33317639, 33229197, 235046422, 33229200, 33229202, 33229204, 33165539, 33165540, 33294010, 33294036, 33294227, 33294232, 33294220, 33294221, 33294222, 33294246, 899836216, 33233796, 221200001, 221200010, 1016786415, 113364238, 3071543043, 144476197, 1027177076, 1027177104, 144476928, 144476934, 144476876, 113358746, 144476812, 920732771, 144477069, 144477089, 144477084, 144477103, 144477233, 151008691, 151008690, 144477138]
Le coût total en électricité de ce chemin est de 325 Wh.
Pour afficher le tracé sur le graph, on ajoute l'attribut edge.inPath a chaque arrete.
### Résultat
Tracé pour le 1
### Comparaison avec Algorithme de GraphStream
Pour évaluer les performances de notre algorithme, nous avons créé une classe de test dans le projet. Cette classe permet de comparer directement notre implémentation du Bellman-Ford avec celle de GraphStream, qui est optimisée et utilise les fonctionnalités internes de la bibliothèque.
On c'est assurer que les résultats de ses 2 algorithmes sont les memes.
#### Résultat
Pour un graphe de la taille de celui du Havre, comprenant 3627 nœuds et 8858 arêtes, on observe que l’algorithme de GraphStream est environ 15 fois plus lent que notre version optimisée.
Dans ce graphique, chaque cluster représente un test avec deux barres :
- Bleu : GraphStream
- Rouge : notre algorithme maison
Les durées sont exprimées en secondes pour plus de lisibilité. Mais on été enregistrer en ms.
#### Commentaire
Comme celui du graph stream nécéssite que chaque arrete est un weight déjà fourni dans le graph. Alors j'ai modifié mon algorithme pour que si le weight existe il nécéssite pas de le calculer en plus. Donc pour qu'il soit sur un pied dégalité