Newer
Older
# 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 intersection 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](src/main/resources/graphe_lehavre.dgs) fournis 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.
Pour commencer avant tout, il faut pouvoir faire une fonction pour ouvrir les fichiers .dgs . Donc on fait Graph getTheFileFromPath(String path) pour récupérer l'objet Graph du fichier
Non les coûts des arêtes ne sont pas fournis. Donc pour calculer le cout on fait une fonction pour une arêtes données retourne qui fait ça :
```java
if (aHauteur<=bHauteur){//donc monte
return (5*(bHauteur-aHauteur)+2f);
}
return ((bHauteur-aHauteur)/2f);
```
#### Résultat
Par exemple, pour l’arête 5 du graphe_grenoble.dgs, cela retourne -4.0 :
---
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 savoir s'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 (descente).
Donc montée + descente = 2. Donc pas de cycle négatif.
L'algorithme le plus adapté pour un parcours de graph avec des coûts d'arêtes négatifs mais sans cycle est l'algorithme de Bellman-Ford.
Sur cette valeur, 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)
## 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
On a implémenté l'algorithme de Bellman-Ford 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 possibles (S'arrêter si pendant une itération il n'y a pas eu de mise à jour) qui change de 2s le temps d'exécutions pour graphe_lehavre.dgs par exemple.
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
```java
public static BellmanFordResult BellmanFord(Graph graph, Node startNode){
Map<Node,Float> mapCost = new HashMap<>();
Map<Node, Node> pred = new HashMap<>();
graph.forEach( node -> {
float value = node == startNode ? 0f: Float.POSITIVE_INFINITY;
mapCost.put(node, value);
pred.put(node, null);
});
AtomicBoolean updated = new AtomicBoolean(true);
for (int k = 1; k < graph.getNodeCount() - 1 && updated.get(); k++) {
updated.set(false);
graph.edges().forEach(edge ->{
float edgeCost = edge.hasAttribute("weight")
? ((Number) edge.getAttribute("weight")).floatValue()
: getCostOfTheArete(edge);
Node sourceNode =edge.getSourceNode();//u
Node targetNode =edge.getTargetNode();//v
if (mapCost.get(sourceNode) +edgeCost<mapCost.get(targetNode)) {
mapCost.put(targetNode,mapCost.get(sourceNode) +edgeCost);
pred.put(targetNode, sourceNode);
updated.set(true);
}
});
}
return new BellmanFordResult(mapCost,pred);
}
```
## 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ée) 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.
On a implémenté la possibilité d'obtenir un chemin et son coût .
Le plus court chemin (au sens de la minimisation de l’électricité consommée) 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 à chaque arête.
2. Il est évident qu'un seul exemple n'est pas représentatif. Pour chacun des graphes fournis, effectuez des tests sur l'algorithme.
#### Application
Pour rendre les tests représentatifs, nous n’avons pas utilisé un seul exemple de nœuds.
- Pour chaque graphe fourni, nous avons exécuté plusieurs tests en choisissant aléatoirement les nœuds de départ et d’arrivée.
- Pour notre algorithme Bellman-Ford, 25 tests ont été réalisés par graphe.
Ainsi, les résultats tiennent compte des variations dues au choix des nœuds et à la structure du graphe. Plus le nombre de tests est élevé moins les variations du pc rentrera en compte.
Voici la courbe des temps d'éxécution de l'ensemble des graphes, généré avec le [script gnuplot](gnuplot/script/plot_courbeAllMyBellman.gnu)
On peut voir les 8 courbes représentant l'ensembles des graphes et durée d'éxécution en micro-seconde.
#### Information supplémentaire
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
| Single-source (S) | All-pairs (A) |
|-----------------|---------------|
| n·m | n²·m |
| Graphe | Nombre de nœuds | Nombre d'arêtes |
|-------------------|----------------|----------------|
| graphe_cherbourg | 13 556 | 32 737 |
| graphe_grenoble | 1 711 | 3 730 |
| graphe_isneauville | 262 | 552 |
| graphe_lehavre | 3 627 | 8 858 |
| graphe_montivilliers | 768 | 1 590 |
| graphe_morlaix | 1 037 | 2 223 |
| graphe_ploemer | 1 441 | 3 163 |
| graphe_rome | 43 223 | 88 831 |
#### Commentaire
On peut observer que le nombre de nœuds et d'arêtes influe directement sur le temps d'exécution.
Cependant, le temps reste exprimé en millisecondes (ms).
Le choix des nœuds de départ et d'arrivée peut également impacter la vitesse de l'algorithme, car certaines distances sont calculées plus rapidement que d'autres, surtout avec l’optimisation “early exit” du Bellman-Ford.
---
3. On souhaite maintenant étudier la version de l'algorithme de Graphstream. Effectuez des tests sur cet algorithme.
#### Application
Pour évaluer les performances de notre algorithme, nous avons créé une [classe de test](src/test/java/org/example/MainTest.java) 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 s’est assuré que les résultats de ses 2 algorithmes sont les mêmes pour assurer que les 2 prennent bien le plus court chemin.
Vu que c'est une comparaison entre 2 algorithme, le choix des Nodes n'est pas important mais doit rester les memes entre les 2 pour bien comparer. Et exécuter les algorithmes
Important : pour l’équité, si une arête possède déjà un attribut weight, nous le réutilisons au lieu de recalculer le coût pour notre algorithme.
Aussi pour limiter au maximum les variations de performance, j'effectue les 2 algorithmes l'un après l'autre pour chaque itération.
Limite : On limite l'exécution à 5 min pour chaque algorithmes sachant qu'il y a 5 tests par graphe sur 2 algorithmes différents.
#### 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é enregistrés en ms.
Chaque test est fait un noeud start et end aléatoire dans le graphe.
On peut donc aussi voir que le temps d’exécution pour chaque noeud n'est pas similaire
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
#### Comprendre pourquoi l'algorithme de GraphStream est lent
Le code de GraphStream utilise une approche récursive pour reconstruire les chemins les plus courts.
On peut voir que la fonction rappelle elle-même pour chaque prédécesseur, créant une copie du chemin à chaque appel.
En conclusion, cette méthode devient très lente sur des graphes larges ou denses, car la récursivité combinée aux multiples copies de chemins fait croître le nombre d’opérations de manière exponentielle avec le nombre de nœuds et de branches.
```java
private void pathSetShortestPath_facilitate(Node current, Path path,
List<Path> paths) {
Node source = graph.getNode(this.source_id);
if (current != source) {
Node next = null;
ArrayList<? extends Edge> predecessors = (ArrayList<? extends Edge>) current
.getAttribute(identifier+".predecessors");
while (current != source && predecessors.size() == 1) {
Edge e = predecessors.get(0);
next = e.getOpposite(current);
path.add(current, e);
current = next;
predecessors = (ArrayList<? extends Edge>) current
.getAttribute(identifier+".predecessors");
}
if (current != source) {
final Node c = current ;
predecessors.forEach(e -> {
Path p = path.getACopy();
p.add(c, e);
pathSetShortestPath_facilitate(e.getOpposite(c), p, paths);
});
}
}
if (current == source) {
paths.add(path);
}
}
```
## Difficulté rencontrée
Lors du TP, nous avons découvert l’importance d’utiliser un timeout pour l’exécution des algorithmes avec GraphStream.
Sans cette protection, certains calculs sur les grands graphes pouvaient bloquer le programme indéfiniment.
L’utilisation de Future et executor.submit() nous a permis de limiter le temps d’exécution et d’éviter que le programme prenne trop de temps.
J'ai découvert et appris comment les utiliser lors de ce TP.
## Conclusion
Ce TP a permis de mettre en pratique plusieurs notions essentielles sur les graphes et les algorithmes de plus courts chemins :
- Manipulation des graphes : ouverture de fichiers .dgs, lecture des nœuds et arêtes, attribution de coûts selon des critères spécifiques.
- Analyse des coûts et choix de l’algorithme : identification des arêtes à coût négatif et sélection de Bellman-Ford comme algorithme adapté pour des graphes sans cycles de coût négatif.
- Implémentation et optimisation : création d’une version maison de Bellman-Ford avec optimisation “early exit”, réduisant considérablement le temps d’exécution.
- Tests et évaluation des performances : exécution de multiples tests sur différents graphes, analyse de la variabilité des temps selon le choix des nœuds et la densité du graphe.
- Comparaison : mise en évidence des limites de l’implémentation de GraphStream, améliorer ma façon de comparer avec pertinence.
En résumé, ce TP a permis non seulement de comprendre la logique des algorithmes de plus courts chemins mais aussi d’appréhender les contraintes de performance liées à la structure des graphes et à l’implémentation de l’algorithme. Il a montré l’importance d’optimiser les algorithmes et de tester leur comportement sur différents scénarios pour obtenir des résultats fiables et efficaces.