GPS Pathfinding: How Does Your Phone Choose the Route?
Every time you ask for directions, your phone solves a graph problem: find the quickest path through a network of roads in a fraction of a second. Build your own network and run the algorithm yourself.
Where this idea comes from
Start here — this is the source that inspired this exploration.
Introduction
A road map is a graph: junctions are vertices, roads are edges, and each edge has a weight — the time it takes to travel. Finding the quickest route from Home to Coffee is exactly the shortest-path problem, and the classic method is Dijkstra's algorithm, which settles the nearest unvisited point step by step until the destination is reached. It is completely doable by hand on a small network, and the same idea (plus some clever shortcuts) runs inside every satnav. Build a network of places you actually go, find your own best routes, and explore what happens when the weights change — that's rush hour. Graph theory here (syllabus topics 3.14 to 3.16) is AI HL content, so if you are doing AI SL or an AA course, treat this as an extension beyond your normal syllabus.
Guiding Questions
- Draw your own journey network — home, school, shops, a friend's house — with realistic travel times on each edge. Find the quickest route between two points by hand. How do you know it's the best?
- Apply Dijkstra's algorithm step by step on your network, recording the order in which vertices are settled. Why can a settled vertex never need revisiting?
- How does the work grow as the network grows? Count the comparisons your algorithm makes on networks of increasing size and look for a pattern.
- Satnavs re-route around traffic. Increase one edge weight mid-journey and see how the best route changes — could you model rush hour with weights that depend on the time of day?