📋 Activity Overview

A Swiggy delivery partner must deliver to 6 houses in Pune. Students draw the city as a graph and find the fastest route — independently discovering Dijkstra's algorithm through structured questioning.

💡 Teacher Tip

Design the city graph so that the intuitive 'obvious' shortest path is NOT actually the shortest when calculated. This cognitive dissonance is what makes the algorithm feel necessary rather than redundant.

🎯 Learning Objectives

  • ✓ Model a real-world navigation problem as a weighted graph
  • ✓ Apply a systematic shortest-path strategy (Dijkstra's algorithm)
  • ✓ Understand greedy algorithms: always choosing the locally best option
  • ✓ Analyse trade-offs: time vs distance vs number of stops

🗂️ Materials Needed

City map worksheet (6 locations, 12 edges with times) Graph paper Coloured pens (3 colours) Distance table template Calculator Ruler

📌 Step-by-Step Instructions

Problem Introduction (5 min) — 'Ravi is a Swiggy delivery partner. He has 6 deliveries and 45 minutes. Help him find the fastest route.' Show the city map with distances in minutes.
Model as Graph (8 min) — Students redraw the city as a graph: circles = locations, lines = roads, numbers = travel time. Discuss: what information is preserved? What is hidden?
Naive Approach (7 min) — Pairs estimate a route intuitively. Try 2–3 different routes and record total time. Which seems best? Can you be sure it's the fastest?
Structured Search (12 min) — Introduce the rule: 'At each step, visit the unvisited location that is reachable in the least total time from the start.' Apply this rule step by step, filling in the distance table.
Compare with Naive (5 min) — Is the structured algorithm's result the same as the intuitive guess? When does intuition fail for graphs with many nodes?
Name the Algorithm (5 min) — Reveal: 'What you just did is called Dijkstra's algorithm. It powers Google Maps, GPS navigation, and network routing.'
Extension (8 min) — Change one edge weight (a road is blocked, takes 3x longer). Rerun the algorithm. Does the shortest path change? This is how Google Maps responds to live traffic data.
Debrief (5 min) — Discuss: greedy algorithms, why they work for shortest paths, and where they don't work (e.g., Travelling Salesman Problem).

🧠 CT Pillar Connections

Algorithmic Thinking
Students discover that intuition fails at scale — a systematic, step-by-step algorithm (Dijkstra's) reliably finds the optimal path even when human intuition misses it.
Abstraction
Converting a city map to a weighted graph is abstraction — roads become edges, locations become nodes, and only travel time is preserved.

💬 Discussion Questions

  • What is the difference between 'shortest distance' and 'fastest route'? When do they differ?
  • How does Google Maps update routes when there is a traffic jam?
  • What would happen if you applied Dijkstra's algorithm to a social network (people as nodes, friendships as edges)?
  • Why can't you always just guess the best route for large graphs?