2026Algorithms & Data Structures
Ghana Road Transport Network
A full-stack solution to the Ghana Road Transport Network Programming Challenge 2026 at Ashesi University. Models Ghana's intercity road network as a graph, implements Dijkstra, Yen's K-Shortest Paths, and cost analysis — exposed via a Java CLI, a Spring Boot REST API, and an interactive Next.js web frontend.
Le Défi
- 6 duplicate bidirectional edges with conflicting weights in the raw dataset
- Efficiently finding top-K loopless shortest paths without modifying the main graph
- Bridging a Java backend and a Next.js frontend with CORS and shared state
La Solution
- Used a LinkedHashMap with case-insensitive town keys; addEdge silently overwrites duplicates to ensure a clean, deterministic graph.
- Implemented Yen's K-Shortest Paths algorithm with a temporary EdgeRemover to spur-path-explore without permanently mutating the graph.
- Configured Spring Boot CORS to allow localhost:3000 and designed a singleton graph bean shared across all API controllers.
Fonctionnalités Clés
- Dijkstra shortest distance and fastest time path (Q4, Q5)
- Yen's Top-3 K-Shortest loopless paths (Q6)
- Fuel and time cost recommendation engine (Q7, Q8)
- Interactive CLI session with multi-query support (Q9)
- Time complexity analysis scaling from 100 to 5,000 nodes (Q10)
- Force-directed interactive network graph with route highlights
- Real-time road editing (add, update, remove) from the browser
Processus
Phase 01
Parsed 557-entry road dataset, deduplicating to clean bidirectional edge set
Phase 02
Built CLI answering all 10 challenge questions (Q1–Q10) via terminal
Phase 03
Wrapped the same Java logic in a Spring Boot REST API (Q1–Q10 endpoints)
Phase 04
Built an interactive Next.js frontend with force-directed graph visualization
Phase 05
Added interactive edge editing (add, update, delete) through the frontend