Click image to open full size
Computer Science
How Online Maps Find Routes
Online Maps Find Routes
Related Tools
Related Labs
Related Worksheets
Online maps find routes by turning a real road network into a graph that a computer can search. Intersections become nodes, and road segments become edges with numbers such as distance, travel time, or traffic cost. This matters because the fastest route is not always the shortest route, especially when speed limits, congestion, and one-way streets are included. A map app must compare many possible paths quickly and choose one that best matches the user's goal.
Key Facts
- A road map can be modeled as a graph: G = (V, E), where V is the set of nodes and E is the set of edges.
- An edge weight can represent distance, time, toll cost, or a combined cost.
- Travel time can be estimated by t = d / v, where d is distance and v is average speed.
- Dijkstra's algorithm finds the lowest-cost path when all edge weights are nonnegative.
- A* search uses f(n) = g(n) + h(n), where g(n) is the cost so far and h(n) is an estimate of remaining cost.
- Live traffic changes edge weights, so a route can be recalculated when conditions change.
Vocabulary
- Graph
- A graph is a structure made of nodes connected by edges, used to model networks such as roads.
- Node
- A node is a point in a graph, such as an intersection, address, or road junction.
- Edge
- An edge is a connection between two nodes, such as a road segment between intersections.
- Weight
- A weight is a number assigned to an edge that measures cost, such as distance or travel time.
- Heuristic
- A heuristic is an estimate that helps an algorithm search toward a goal more efficiently.
Common Mistakes to Avoid
- Treating the shortest distance as always the fastest route is wrong because speed limits, traffic, turns, and stops can make a longer route quicker.
- Ignoring one-way streets is wrong because graph edges may have direction, so a road can be usable from A to B but not from B to A.
- Using straight-line distance as the actual road distance is wrong because roads curve, detour, and may not connect directly.
- Assuming route calculations never change is wrong because edge weights can update when traffic, construction, crashes, or closures appear.
Practice Questions
- 1 A road segment is 6 km long and the average speed is 40 km/h. What is the estimated travel time in minutes?
- 2 A route has edge travel times of 4 min, 7 min, 3 min, and 6 min. A second route has edge travel times of 5 min, 5 min, 5 min, and 4 min. Which route is faster and by how many minutes?
- 3 Explain why an online map might recommend a route that is longer in kilometers than another available route.