09 / Graph routing system
Transportation Planner
A C++ routing system that parses OpenStreetMap data and computes explainable paths with Dijkstra and A*.
GitHub · View repository ↗RoleAlgorithm and systems implementation
PeriodUC Davis course project
StatusCompleted
The Challenge
Transform real map data into a searchable graph while balancing correctness, performance, and testability.
Approach
- Parsed XML / CSV into nodes and edges
- Implemented Dijkstra and heuristic A*
- Validated paths with small graphs and boundary inputs
System Structure
- Data parsing and normalization
- Adjacency graph and priority queue
- Path search and result reconstruction
Outcomes
- Completed an end-to-end routing flow
- Achieved O(E log V) search complexity
- Compared two classic shortest-path strategies
Discuss this project
Interested in this project’s methods, implementation, or tradeoffs? I welcome a conversation by email.