Projects / Computer Science / Computer Science project 48

Route Planner Using Dijkstra and A* on OpenStreetMap

Approx. component budget: Rs. 0 - 500

Objective

Compare path-finding algorithms on a real road network and measure the speed gain from smarter search.

What you will build

A map app that finds the shortest or fastest route between two points in your city using real road data and shows the visited nodes of each algorithm.

Results you can expect

• Route length and travel time vs Google Maps for 20 trips
• Nodes explored by Dijkstra vs A*
• Computation time
• And effect of road closures

What you will learn

Graph algorithms, heuristics, real map data, and visualisation on a web map.

Tools and notes

Python with OSMnx and NetworkX or C++, OpenStreetMap data, Leaflet. Respect the OSM licence and credit the data.

Resume points from this project

• Built and tested Route Planner Using Dijkstra and A* on OpenStreetMap; objective: compare path-finding algorithms on a real road network and measure the speed gain from smarter search.
• Measured and analysed route length and travel time vs Google Maps for 20 trips and nodes explored by Dijkstra vs A*; wrote the report and presented the results in a viva. Add your own numbers: [x].

Replace [x] with your own measured results. Write only what you really did.

More computer science projects

Back to all projects