function route(map: RoadMap, start: Node, goal: Node) {const queue = [start], hops = new Map([[start, 0]]), parent = new Map();
while (queue.length > 0) {// the oldest intersection in the queue
const current = queue.shift()!;
if (current === goal) return rebuild(parent, goal);
for (const street of map.streetsFrom(current)) {const next = street.otherEnd(current);
const candidate = hops.get(current)! + 1;
if (hops.has(next)) continue;
hops.set(next, candidate); parent.set(next, current);
queue.push(next);
}
}
}
Loading the street map…
Understanding BFS on the real map
The idea
Breadth-first search treats every street segment as one hop, whatever its length. It expands the intersections in rings: all the ones one hop away, then two, then three, and stops when the goal is dequeued. The route it returns crosses the fewest intersections.
That is not the shortest route in metres. A few long blocks along an avenue count the same as many short ones downtown, so BFS happily takes the long way round. Compare its route length with Dijkstra's on the same start and goal: the difference is the price of ignoring the weights.
The four stages
Complexity
Versus its siblings
Pseudocode
ROUTE(map, start, goal)
queue ← [start]; hops[start] ← 0
while queue not empty
current ← dequeue the oldest
if current = goal: return the route via parent
for each street leaving current, to an unseen neighbour
hops[neighbour] ← hops[current] + 1; parent[neighbour] ← current; enqueue neighbour
When to use
Pitfalls
History
The map is the centre of Cascavel, Paraná: 4 180 intersections and 5 438 street segments from OpenStreetMap, one-way streets respected, about 10 by 7 km. Every real routing engine runs this same loop on a graph a million times larger, with contraction hierarchies or landmarks precomputed so that a query touches only a sliver of it.