# 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. #### Application 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. ```java public static BellmanFordResult BellmanFord(Graph graph, Node startNode){ Map mapCost = new HashMap<>(); Map 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 paths) { Node source = graph.getNode(this.source_id); if (current != source) { Node next = null; ArrayList predecessors = (ArrayList) 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) 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.