A graph-based navigation system that models Ontario's road network and finds efficient routes between any two locations using a custom greedy recursive pathfinding algorithm.
Built as a final project for CSC111 (Fundamentals of Computer Science II) at the University of Toronto, Winter 2025.
Route visualization at different search depths (depth 3 → 30):
| Depth 3 | Depth 5 |
|---|---|
 |
 |
| Depth 10 | Depth 30 |
|---|---|
 |
 |
Higher depth = more explored neighbors = smoother, more accurate routes.
The program models Ontario's road network as a graph, where:
- Vertices → traffic junctions (with latitude/longitude)
- Edges → roads (with speed limit, length, direction, and highway flag)
Rather than a standard Dijkstra's (which would be too slow on this dataset), we designed a custom greedy recursive navigation algorithm:
- From the current junction, explore all neighbors up to a configurable depth using a modified DFS.
- For each reachable junction, compute a "speed of approach" score:
score = (distance_reduced_toward_target) / (time_to_reach_junction) - Greedily move to the junction with the highest score.
- Repeat recursively until the destination is reached.
This significantly reduces computation by avoiding exhaustive graph traversal, at the cost of not guaranteeing a globally optimal path — a reasonable tradeoff for large real-world datasets.
Road network data from the Ontario Road Network (ORN) via Ontario GeoHub:
ORN_JUNCTION.csv— junction ID, latitude, longitude, typeORN_ROAD_NET_ELEMENT.shp— road geometry, length, directionORN_SPEED_LIMIT.csv— speed limits per road segment
Data is preprocessed into .pkl files for fast loading via Python's pickle library.
pip install -r requirements.txtDownload the pre-generated data files here: https://drive.google.com/drive/folders/15IDu_pCN3SefWsWfm9b8o7REMgJP0tVT?usp=share_link Place junction_data.pkl and road_data.pkl in the project root directory.
python main.pyFollow the prompts:
- Start/End location: Enter latitude and longitude to 5 decimal places, space-separated
- Example:
43.91963 -79.47427
- Example:
- Include highway:
yesorno - Search depth: Integer (recommended:
10)
pathfinder/
├── main.py # Entry point — handles user input and orchestrates navigation
├── Load_graph.py # Core module: graph ADT, pathfinding algorithm, visualization
├── requirements.txt # Python dependencies
├── junction_data.pkl # Preprocessed junction data (not included — see setup)
├── road_data.pkl # Preprocessed road data (not included — see setup)
└── assets/ # Screenshots for README
| Class / Function | Description |
|---|---|
Vertex |
Represents a road junction with position and connected roads |
Road |
Represents a road edge with speed limit, length, and highway flag |
Graph |
Adjacency-dict graph containing all junctions and roads |
Navigation |
Wraps a pathfinding request; stores route and map context |
better_recursive_navigation |
Core recursive greedy pathfinding algorithm |
better_neighbour_search |
Depth-limited DFS to explore reachable neighbors |
visualize_map |
Renders the route on a map using NetworkX + Matplotlib |
direction |
Converts junction sequence into turn-by-turn directions (left/right/straight) |
find_near_junc |
Finds the nearest graph junction to a given coordinate |
networkx— graph renderingmatplotlib— visualizationgeopandas— shapefile parsingpython-ta— code style checking
- The greedy algorithm is not guaranteed to find the globally optimal path — it can miss routes that require temporarily moving away from the destination.
- Depth is a key accuracy-vs-performance tradeoff parameter. A depth of 10 provides a good balance.
- Future improvements could include:
- Address/street name input instead of raw coordinates
- Interactive map output (e.g., Folium or Plotly)
- Travel time estimation displayed to the user
- A proper implementation of A* or bidirectional Dijkstra for optimal routing
- Adish Singh
- Mohan Sun
University of Toronto — CSC111, Winter 2025