algorithmsCSapplied-math

From Routes to Algorithms: Teaching A* and Heuristics with Real Navigation Data

eequations

2026-02-02

9 min read

Use Google Maps vs Waze routing differences to teach A*, heuristics, and routing. Hands-on labs, code outlines, and 2026 trends for classroom use.

Hook: Why your students get different answers from Google Maps and Waze — and why that’s a teaching goldmine

Students and teachers often sit with the same frustration: two “trusted” navigation apps give different routes and different estimated times of arrival. That mismatch feels arbitrary — but it’s actually an excellent window into the design choices, objective functions, and heuristics that power modern pathfinding. Use this tension as a springboard to teach Teaching A* and heuristic design with real navigation data, hands-on experiments, and simulations that map classroom math to real-world decision-making.

Why Google Maps and Waze choose different routes (a practical overview for students)

Before coding A*, ground students in the observable differences and plausible causes. Ask them to make predictions, then test.

Different objective functions: Google Maps often optimizes for a blend of predicted travel time and reliability, while Waze (community-driven) may aggressively avoid reported incidents even if the alternate route is slightly longer.
Data sources and latency: Google integrates historical traffic, real-time sensor and user telemetry, and third-party feeds. Waze uses crowd-sourced user reports and high-signal community updates—sometimes faster for incidents.
Personalization and A/B experiments: Both platforms run continuous experiments and can personalize routes based on your driving history, time of day, and user settings.
Routing constraints: One app might prefer highways; another favors local streets to avoid congestion or tolls. Road closures, turn restrictions, and vehicle-type rules differ between providers. Some routing stacks are even deployed on low-latency edge instances to reduce recomputation, which changes trade-offs in practice—see lightweight deployments on micro-edge VPS.
Multi-criteria trade-offs: Distance, ETA, fuel efficiency, and user comfort can be weighted differently; those weights are effectively the app’s heuristic and cost model.

“Two different routes from two trusted sources are not mistakes — they’re alternative optimal choices under different cost models.”

From routes to algorithms: A crisp A* refresher with classroom-friendly pseudocode

Use this section to make sure students know the core mechanics before tweaking heuristics.

Core idea

A* finds a lowest-cost path from start to goal on a graph by combining: g(n) = cost so far, and h(n) = heuristic estimate of remaining cost. The algorithm expands nodes in increasing order of f(n) = g(n) + h(n).

Teaching-friendly pseudocode

function AStar(start, goal, h):
  open = priority_queue()  // order by f = g + h
  open.insert(start, f=start.g + h(start))
  closed = set()

  while open not empty:
    current = open.pop()  // node with smallest f
    if current == goal: return reconstruct_path(current)
    closed.add(current)
    for neighbor in neighbors(current):
      tentative_g = current.g + cost(current, neighbor)
      if neighbor in closed and tentative_g >= neighbor.g:
        continue
      if tentative_g < neighbor.g or neighbor not in open:
        neighbor.g = tentative_g
        neighbor.parent = current
        neighbor.f = neighbor.g + h(neighbor)
        if neighbor not in open:
          open.insert(neighbor, neighbor.f)
  return failure

Key classroom points: admissibility (h never overestimates true remaining cost) guarantees optimality; consistency means h(u) ≤ cost(u,v)+h(v) and simplifies reasoning and implementation.

Designing heuristics: from Euclidean to traffic-aware and learned

Let students design and compare heuristics. Walk through progressively richer estimators so they see how domain knowledge improves search efficiency.

1) Straight-line heuristic (Euclidean / Haversine)

On road graphs with latitude/longitude, the straight-line distance lower-bounds travel distance. Use the Haversine formula to compute great-circle distance d between two coordinates.

function haversine(lat1, lon1, lat2, lon2):
  // returns kilometers between points on Earth
  ... // standard formula
  return d

A simple heuristic for travel time: h(n) = d(n, goal) / vmax where vmax is an optimistic max speed (e.g., 130 km/h for highways). Choosing vmax too high still keeps admissibility but reduces pruning effectiveness.

2) Grid-style heuristics (Manhattan)

On gridded street layouts, Manhattan distance (|dx|+|dy|) is informative and admissible when movement is axis-aligned.

3) Speed-aware heuristic (time estimate)

Use historical speed profiles per road class: h(n) = sum_{segments} segment_length / expected_speed(segment). For a fast approximate, estimate remaining time ≈ d(n,goal) / avg_network_speed. This is still admissible if avg_network_speed is an optimistic upper bound.

4) Traffic-augmented heuristics

Incorporate recent incident layers or live congestion multipliers. If you use live data, be careful about admissibility — traffic delays can make a heuristic optimistic or pessimistic. For guaranteed optimality, ensure the heuristic underestimates true travel time.

5) Learned heuristics (2023–2026 trend)

Recent research and industry pilots (2022–2025) show learned heuristics — small neural nets predicting remaining travel time from graph features — can reduce node expansions dramatically. In classrooms, present a simplified workflow: train a regression model on past trips to predict travel time-to-go and use the model’s prediction as h. Stress that unless the model is conservatively adjusted, it may overestimate and break optimality guarantees; instead teach students to deploy learned heuristics as guide functions in algorithms like weighted A* or as tie-breakers.

Hands-on classroom lab: Compare live Google Maps and Waze routes, then simulate

This lab turns observation into computation. The goal: explain why the apps differ by reproducing aspects of their cost models in a controlled A* simulation using OpenStreetMap (OSM) extracts and routing toolkits.

Materials and ethical notes

Accounts and API keys: Use official APIs (Google Maps Platform) and Waze for Cities / Waze data partnership tools where permitted. Do not scrape interfaces; check terms.
Open data: Use OpenStreetMap extracts and routing engines like OSRM, GraphHopper, or the Python library osmnx + networkx for classroom graphs.
Privacy: Use anonymized routes; avoid collecting PII. If using live student devices, get consent and limit telemetry.

Step-by-step lab (90–120 minutes)

Pick 10 origin-destination pairs in your city showing variety (urban, suburban, highway). Record the time of day.
Query Google Maps and Waze simultaneously for each pair and log: ETA, distance, chosen route geometry, and any incident notes.
Load the corresponding OSM subgraph (use bbox around routes). Convert to a directed weighted graph where edge weights = travel time estimate (length/speed_limit).
Implement A* with three heuristics: (a) Haversine/vmax, (b) Haversine/avg_speed, (c) learned regressor on past OSM traces (optional advanced task).
Run A* and compare the chosen route (edges sequence), ETA, and number of node expansions against both apps. Visualize on a map.
Analyze mismatches: where did A* pick the same path as Google Maps or Waze? Which heuristic best predicts each app’s choice? Form hypotheses about the internal cost model.

Sample code outline (Python + networkx)

# using osmnx to get graph
G = ox.graph_from_bbox(north, south, east, west, network_type='drive')
# add travel time weight
for u,v,key,data in G.edges(keys=True, data=True):
    data['travel_time'] = data['length'] / (data.get('maxspeed', default_speed))

# implement A* using networkx.astar_path with custom heuristic
path = nx.astar_path(G, source, target, heuristic=h, weight='travel_time')
# measure node expansions by instrumenting the open set

Practical assessment: ask students to produce a report that explains, with quantitative metrics, which heuristic best matches Google Maps and which matches Waze across your sample trips. Consider adding an instrumentation pipeline so students can log expansions and visualize them with lightweight observability tooling like an observability-first dashboard.

Dynamic environments: replanning, D* and weighted A*

Real navigation is dynamic. Teach these follow-ups:

Replanning: When live traffic changes, algorithms must replan. Introduce D* Lite for efficient incremental replanning when edge costs change. For classroom demos, consider running parts of the stack on micro-edge VPS to show latency differences.
Weighted A*: Using f = g + ε·h speeds search for near-optimal paths. Explain the trade-off between optimality and speed and how apps sometimes intentionally favor faster replanning.
Multi-criteria routing: Real systems optimize for ETA, distance, tolls, and driver preferences. Show how Pareto frontiers capture non-dominated trade-offs and how apps pick a point from that frontier.

Advanced classroom topics & 2026 trends you should teach now

Bring students up to date on how research and industry are evolving routing systems as of 2026.

Learned heuristics go mainstream: Between 2022–2025, research prototypes showed that small neural networks trained on historical trips reduce expansions and latency. By 2026, hybrid systems that combine classical heuristics with lightweight learned components are increasingly common in production.
Privacy-preserving traffic analytics: Federated and synthetic data approaches gained traction in late 2025 to allow routing systems to improve without centralizing raw user traces.
Edge inference and real-time adaptation: Edge deployments allow faster rerouting and local incident detection, a trend accelerated by vehicle telematics and 5G edge compute rollout in 2025–2026.
Open routing ecosystems: Projects such as OpenStreetMap, OSRM, GraphHopper, and MapLibre continue providing high-fidelity graph data and routing toolkits for teaching and research.
Autonomy & multimodal planning: As autonomous vehicles and micromobility become more common, routing must reason across vehicle models and network constraints — making heuristic design more complex and interesting.

Assessment tasks, challenge problems and grading rubric

Use these to evaluate mastery.

Proof task: Prove why the straight-line heuristic is admissible on road networks and show a counterexample where h overestimates causing suboptimality.
Implementation task: Implement A* with Haversine/h_max and measure nodes expanded vs Dijkstra on five OSM routes.
Design task: Propose a traffic-aware heuristic, implement it, and compare its predictive power for Google Maps vs Waze choices using your lab dataset.
Advanced challenge: Train a lightweight regressor for time-to-go and use it as a guide in weighted A*; report trade-offs between optimality and speed.

Rubric (high-level): Correctness (40%), Efficiency & analysis (30%), Report & visualization (20%), Creativity & insight (10%).

Actionable teaching tips and classroom scaffolding

Start with paper maps: have students manually trace routes and define cost models before coding.
Use small graphs first (grid city block) to show node expansion patterns visibly.
Instrument A* to log expansions and frontier sizes — visualizing search is a huge learning win. Pair that instrumentation with lightweight dashboards or export templates to simplify student reports (see visualization templates).
Encourage hypothesis-driven exploration: predict which app will match which heuristic, then test.
For advanced classes, assign a short reading brief on learned heuristics and have students present the trade-offs between accuracy and admissibility.

Resources and safe data practices

Recommended tools and datasets:

OpenStreetMap (OSM) extracts for your city — great for building graphs.
osmnx + networkx for Python-based graph retrieval and A* experiments.
OSRM / GraphHopper for server-side route simulation.
Google Maps Platform and Waze for Cities — use official APIs and data partnership channels with permission.

Compliance note: always check API terms and avoid scraping app UIs. Use anonymized or synthetic data when sharing student work publicly.

Key takeaways: What students should walk away knowing

Practical insight: Different routes are manifestations of different cost functions and heuristics — not errors.
Algorithmic mastery: A* is an efficient and flexible baseline; heuristics drive performance and must be designed with admissibility in mind when optimality is required.
Real-world complexity: Live routing introduces dynamics (incidents, personalization, experiments) that demand replanning, multi-criteria optimization, and sometimes learned components.
2026 readiness: Students should be aware of learned heuristics, federated privacy techniques, and edge compute trends that shape modern routing systems.

Call to action

Ready to turn this lesson into a classroom lab? Download the starter notebook and OSM extracts for your city, or sign your school up for a guided workshop (includes reproducible A* simulations, grading rubrics, and visualization templates). Put the disagreement between Google Maps and Waze to work — teach heuristic thinking from day one.

equations

Contributor

Senior editor and content strategist. Writing about technology, design, and the future of digital media. Follow along for deep dives into the industry's moving parts.