Dijkstra vs A* route planning: an interactive shortest path visualizer

Route planning is a shortest-path search on a graph: intersections are nodes, road segments are edges weighted by travel time. Dijkstra’s algorithm finds the fastest route by exploring outward in order of travel time. A* finds the same route while exploring far less, by steering towards the goal with an estimate of the time left. Real map services go further and precompute shortcuts, so a cross-continent query touches only a few hundred nodes.

The playground plans the same trip three ways on a city grid with a river and a congested zone. Pick a trip or click the map to move the start and goal.

Dijkstra, A* and bidirectional search

Dijkstra expands intersections in order of their travel time from the start, so before it reaches a goal 30 minutes away it has visited everything closer than 30 minutes in every direction: 338 of the grid’s intersections for the trip across the river. A* orders them by time so far plus an estimate of the time left, here the straight-line distance in blocks, and visits 111. The estimate must never overestimate, or A* can miss the best route; on real roads it is the straight-line distance divided by the highest speed limit. Searching from both ends at once, which is how many production routers start, meets in the middle and on large road networks visits roughly half as much as one-directional Dijkstra.

The estimate helps most when the route is roughly a straight line: 7 intersections instead of 49 for a short trip. From corner to corner of the grid, nearly every intersection is on some plausible route, and A* visits 333 against Dijkstra’s 365.

How map services answer in milliseconds

A continental road graph has tens of millions of nodes, and even A* is too slow for millions of queries. Production routers precompute. Contraction hierarchies rank nodes by importance and add shortcut edges that skip unimportant ones, so a query only ever climbs to important roads and back down, touching hundreds of nodes. Customizable variants split the graph into cells and precompute paths across each cell, so live traffic can update edge weights every few minutes without redoing the whole preprocessing. Travel times themselves come from historical speeds per road segment and time of day, corrected by live probe data from phones and vehicles.

A* in code

import heapq

def a_star(graph, start, goal, h):
    """graph[n] -> [(neighbour, minutes)]; h(n) must never overestimate the minutes left."""
    best = {start: 0}
    came_from = {}
    frontier = [(h(start), start)]
    while frontier:
        _, node = heapq.heappop(frontier)
        if node == goal:
            break
        for nxt, minutes in graph[node]:
            cost = best[node] + minutes
            if cost < best.get(nxt, float("inf")):
                best[nxt], came_from[nxt] = cost, node
                heapq.heappush(frontier, (cost + h(nxt), nxt))   # h = 0 gives Dijkstra
    path = [goal]
    while path[-1] != start:
        path.append(came_from[path[-1]])
    return best[goal], path[::-1]

In a system design interview

For a maps or ride-hailing design, separate the graph from the queries: “The road graph is partitioned into cells and preprocessed offline into a multi-level overlay. Live traffic updates edge weights per cell every few minutes. A routing query runs a bidirectional search over the overlay, so it touches a few thousand nodes and returns in tens of milliseconds; ETAs come from the same weights, adjusted by a model trained on completed trips.” Expect the follow-ups: turn restrictions, alternative routes, and how traffic data is collected and smoothed.

Read the guide to routing and shortest paths or large-scale graph processing, see geohashes for finding the nearest road, or watch a strong candidate design Google Maps.

Questions people ask