Réseau Routier du Ghana
01. Vue d'ensemble
Solution full-stack du challenge Ghana Road Transport Network 2026: modélisation graphe, Dijkstra, Yen K-shortest paths, API Spring Boot, CLI Java et frontend Next.js interactif.
Objectif
Modéliser le réseau routier interurbain du Ghana et fournir des outils de parcours, estimation de coûts et gestion de connectivité.
Résultat
Système multi-couches robuste couvrant les 10 questions du challenge avec visualisation force-directed et édition en temps réel des routes.
02. Stack technique
03. Fonctionnalités clés
Distance la plus courte et chemin le plus rapide via Dijkstra (Q4, Q5)
Top-3 chemins les plus courts sans boucle via Yen (Q6)
Moteur de recommandation de coûts carburant/temps (Q7, Q8)
Session CLI interactive multi-requêtes (Q9)
Analyse de complexité de 100 à 5 000 nœuds (Q10)
Graphe réseau interactif avec mise en évidence des routes
Édition des routes depuis le navigateur
04. Pipeline d'ingénierie
Parsing du dataset routier (557 entrées) avec déduplication vers un ensemble propre d'arêtes bidirectionnelles
Développement d'un CLI répondant aux 10 questions du challenge (Q1-Q10)
Exposition de la même logique Java via API REST Spring Boot (endpoints Q1-Q10)
Création d'un frontend Next.js interactif avec visualisation force-directed
Ajout de l'édition des routes en temps réel (ajout, mise à jour, suppression)
05. Défis & exécution
Contrainte
6 arêtes bidirectionnelles dupliquées avec poids conflictuels dans le dataset brut
Exécution
Utilisation d'un LinkedHashMap avec clés de villes insensibles à la casse; addEdge écrase les doublons pour garder un graphe déterministe.
Contrainte
Trouver efficacement les K meilleurs chemins sans boucle sans modifier le graphe principal
Exécution
Implémentation de l'algorithme de Yen avec un EdgeRemover temporaire pour explorer les spur paths sans mutation permanente.
Contrainte
Relier un backend Java et un frontend Next.js avec CORS et état partagé
Exécution
Configuration CORS Spring Boot pour localhost:3000 et conception d'un bean singleton de graphe partagé par tous les contrôleurs API.