How does navigation find the best route? Dijkstra and A* | Curious Engineering #03

Instructor: Dr. Süleyman Burak ÇELİK

Why can a longer route suggested by navigation be faster? Starting with a synthetic 3D city and two bridges, we build the route-finding process step by step. We define the journey's cost, turn intersections into nodes and roads into weighted edges, then follow Dijkstra on a six-node directed example. The priority queue, edge relaxation and reconstruction of the route from predecessor records become visible as the search unfolds. For A*, we examine the priority f = g + h, a time lower bound built from straight-line distance divided by maximum speed, and the conditions of admissibility and consistency. Separate examples show how overestimating can miss the best route, how closing a bridge changes the problem, and why negative weights call for a method such as Bellman–Ford. We finish with turn restrictions, data structures and larger road networks. The city example's 100-versus-72 comparison counts examined nodes only; it is not real traffic data or a speed measurement of a navigation product.