2026Algorithmes & Structures de Données
Réseau Routier du Ghana
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.
Le Défi
- 6 arêtes bidirectionnelles dupliquées avec poids conflictuels dans le dataset brut
- Trouver efficacement les K meilleurs chemins sans boucle sans modifier le graphe principal
- Relier un backend Java et un frontend Next.js avec CORS et état partagé
La Solution
- Utilisation d'un LinkedHashMap avec clés de villes insensibles à la casse; addEdge écrase les doublons pour garder un graphe déterministe.
- Implémentation de l'algorithme de Yen avec un EdgeRemover temporaire pour explorer les spur paths sans mutation permanente.
- Configuration CORS Spring Boot pour localhost:3000 et conception d'un bean singleton de graphe partagé par tous les contrôleurs API.
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
Processus
Phase 01
Parsing du dataset routier (557 entrées) avec déduplication vers un ensemble propre d'arêtes bidirectionnelles
Phase 02
Développement d'un CLI répondant aux 10 questions du challenge (Q1-Q10)
Phase 03
Exposition de la même logique Java via API REST Spring Boot (endpoints Q1-Q10)
Phase 04
Création d'un frontend Next.js interactif avec visualisation force-directed
Phase 05
Ajout de l'édition des routes en temps réel (ajout, mise à jour, suppression)