Routing on road networks

Every navigation app is running some form of shortest-path search on a graph of roads. The specific algorithm depends on the scale, but the underlying model is always the same.

Roads as a graph

A road network is a directed weighted graph:

• Nodes: intersections, dead ends, POIs
• Edges: road segments with direction and weight (travel time or distance)
• Weights: computed from speed limits, road type, traffic, turn costs

const graph = {
  "A": [{ to: "B", weight: 5 }, { to: "C", weight: 10 }],
  "B": [{ to: "D", weight: 3 }],
  "C": [{ to: "D", weight: 2 }],
  "D": [],
};

One-way streets become single-direction edges. A two-way road is two edges with the same weight.

Dijkstra's algorithm

Finds the shortest path from a source to all other nodes:

function dijkstra(graph, start, end) {
  const dist = {}, prev = {}, visited = new Set();
  const queue = new MinHeap();

  dist[start] = 0;
  queue.push({ node: start, cost: 0 });

  while (!queue.isEmpty()) {
    const { node, cost } = queue.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    if (node === end) break;

    for (const { to, weight } of graph[node] ?? []) {
      const newCost = cost + weight;
      if (newCost < (dist[to] ?? Infinity)) {
        dist[to] = newCost;
        prev[to]  = node;
        queue.push({ node: to, cost: newCost });
      }
    }
  }

  // Reconstruct path
  const path = [];
  let cur = end;
  while (cur) { path.unshift(cur); cur = prev[cur]; }
  return path;
}

Time complexity: $O((V + E) \log V)$ with a min-heap.

A* — Dijkstra with direction

A* adds a heuristic $h(n)$ — an estimate of the remaining cost from node $n$ to the goal. For geographic routing, the straight-line distance (Haversine) is a perfect admissible heuristic:

function heuristic(nodeA, nodeB) {
  return haversine(nodeA.lat, nodeA.lon, nodeB.lat, nodeB.lon);
}

// In the main loop, replace cost with f = g + h:
queue.push({ node: to, cost: newCost + heuristic(nodes[to], nodes[end]) });

A* explores far fewer nodes than Dijkstra — typically 5–10× faster for geographic routing because it focuses the search toward the destination.