GPS Navigation

Graph Theory · Axiom Academy

How graph theory powers every route your GPS finds Every time you tap "Navigate" on your phone, something remarkable happens. Your GPS doesn't just draw a line from point A to B—it solves a complex mathematical problem using graph theory . Behind the scenes, your navigation app models the entire road network as a weighted graph : Intersections become vertices (nodes) Roads become edges connecting vertices Travel time or distance becomes weights on edges Let's explore how this works with an interactive city map. Below is a simplified city map. Each circle is an intersection (vertex), and each line is a road (edge) with a weight representing travel time in minutes. Click "Find Route" to see how the GPS calculates the fastest path from Home (blue) to Work (green). You just saw the GPS find the fastest route in seconds. But here's the challenge: with 6 intersections and 9 roads, there are many possible paths! How does the GPS efficiently find the best route among all possibilities? Dijkstra's Algorithm in Action GPS systems use Dijkstra's algorithm (or its modern variant A*) to find the shortest path. Here's how it works: Start at your current location (source vertex) Explore all neighboring intersections, tracking the total time to reach each Always pick the shortest unexplored path next (greedy approach) Update distances as you discover shorter routes Repeat until you reach your destination The mathematical notation for the shortest path from vertex s to vertex t :

This is the written version of the interactive lesson above. See the full Graph Theory course.