04 / Graph routing system
Transportation Planner.
A C++ routing system that parses OpenStreetMap data and computes explainable paths with Dijkstra and A*.
RoleAlgorithm and systems implementation
PeriodUC Davis course project
StatusCompleted
01 / The challenge
Transform real map data into a searchable graph while balancing correctness, performance, and testability.
02 / Approach
- Parsed XML / CSV into nodes and edges
- Implemented Dijkstra and heuristic A*
- Validated paths with small graphs and boundary inputs
03 / System structure
- Data parsing and normalization
- Adjacency graph and priority queue
- Path search and result reconstruction
04 / Public outcomes
What the work established.
- Completed an end-to-end routing flow
- Achieved O(E log V) search complexity
- Compared two classic shortest-path strategies