Head office, Rana Pratap Bagh, Delhi011 2721 1512+91 97116 99511

Science project idea

City bus route and fare finder using Dijkstra’s algorithm on a graph

Commuters in a town often do not know which buses to take or where to change. Modelling stops as nodes and bus links as weighted edges lets Dijkstra’s algorithm find the shortest or cheapest route. The project builds the graph from a published route list and shows the route on a map web page.

Make it yourself12 numbered steps, the materials and the science, all free.Go to the stepsGet a ready-made kitReady-made models, kits and spare parts in the store under Engineering Projects.Browse Engineering ProjectsAsk on WhatsAppAsk the head office whether a model or kit for this idea is available.Send a message

What it shows

Commuters in a town often do not know which buses to take or where to change. Modelling stops as nodes and bus links as weighted edges lets Dijkstra’s algorithm find the shortest or cheapest route. The project builds the graph from a published route list and shows the route on a map web page.

The science

Dijkstra’s algorithm keeps the best known distance to each node, repeatedly selects the unvisited node with the smallest distance and relaxes its edges. With a priority queue its time is O((V + E) log V). Edge weights can be travel time, distance or fare, and an extra penalty for changing buses gives routes with fewer transfers. Weights must not be negative.

Materials

Cost: free. Many items come from home or from waste; spare parts such as LEDs, motors and wire are in the store.

  • A laptop with Python 3 and Flask
  • A published bus route and stop list of your town (written from public timetables), 20 to 40 stops and 8 routes
  • The Leaflet library for maps loaded from a CDN, with OpenStreetMap tiles
  • Latitude and longitude for each stop from a free map
  • A notebook for diagrams

Safety

For this project: Check the timetable data from public sources. Do not collect data from private people. Mention that the app is a student project.

Never use mains electricity: power models with cells, batteries or a low-voltage adapter. Sharp and hot tools, flames and lab chemicals need an adult or your teacher beside you. Keep magnets, button cells and small parts away from young children, and wash your hands after making.

All the safety rules

Step by step

12 steps. Do them in order, and test each part before you go on to the next. Write what you notice in a notebook as you go.

  1. Collect the stops with coordinates and the routes as ordered stop lists with travel time between stops.

  2. Store them in CSV files and write code to load them into a graph using a dictionary of adjacency lists.

  3. Represent each stop on each route as a node so that a change of bus can be given a time penalty.

  4. Implement Dijkstra with the heapq module and test it on a small example calculated by hand.

  5. Add path reconstruction to return the list of stops and the buses used.

  6. Write the fare function from the published fare slabs, for example by number of stops.

  7. Add a mode switch: fastest, fewest changes or cheapest, by changing the weights.

  8. Build a Flask page with two drop-downs for the origin and destination stops.

  9. Draw the chosen route on a Leaflet map with markers and a line, and list the steps below it.

  10. Test 30 origin and destination pairs against a human-planned route and note the differences.

  11. Measure the run time for graphs of 100, 1,000 and 10,000 nodes created randomly.

  12. Write the report with the algorithm, complexity, screens, test results and limits.

What you should see

The app returns routes in under a second, matches human-planned routes in most test pairs, and the run time grows slightly faster than linearly with graph size, as the theory predicts.

Viva questions

A teacher or a judge will ask how it works. Try to answer each question before you open it, then compare.

1Why does Dijkstra not work with negative weights?

It assumes that once a node is settled its distance cannot be improved, which fails if later edges can reduce it.

2What data structure makes it efficient?

A priority queue (heap) that gives the smallest distance node quickly.

3How did you model changing buses?

Each stop on each route is a separate node, with a transfer edge of extra time between route nodes at the same stop.

4How is this different from BFS?

BFS finds the fewest edges, while Dijkstra finds the smallest total weight.

Free ebook: Viva Questions for Science Projects

Take it further

Add time-of-day schedules so that waiting time for the next bus is added to each change.

Change one thing, measure what happens, and add a table or chart of your readings: that is what turns a model into your own investigation.

Free ebooks for this project

WhatsApp us