Home/Pathfinding/Dijkstra on the real map
Search algorithmsCTRL K

Dijkstra on the real map

· Cascavel streets · no heuristic
RUN WITH
A*DijkstraBFS
/pathfinding/real-map-dijkstra
EXPANDED
intersections closed
OPEN
intersections waiting
DISTANCE
start to the current one
ROUTE
length once found
STRAIGHT LINE
start to goal
explored streets · opencurrentroutestart / goal
Click the map: first the start, then the goalLoading the street map…
step 0 / 0
Route (×100 m)20
route_dijkstra.ts
1
function route(map: RoadMap, start: Node, goal: Node) {
2
  const open = new MinHeap([start]), distance = new Map([[start, 0]]), parent = new Map();
3
  while (open.size > 0) {
4
    // lowest distance so far
5
    const current = open.pop();
6
    if (current === goal) return rebuild(parent, goal);
7
    for (const street of map.streetsFrom(current)) {
8
      const next = street.otherEnd(current);
9
      const candidate = distance.get(current)! + street.metres;
10
      if (candidate >= (distance.get(next) ?? Infinity)) continue;
11
      distance.set(next, candidate); parent.set(next, current);
12
      open.push(next, candidate);
13
    }
14
  }
15
}
CURRENT STEP
line 1

Loading the street map…

// how it works

Understanding Dijkstra on the real map

Dijkstra · the disc of closest intersections grows until it touches the goal
01

The idea

Dijkstra always closes the open intersection with the shortest driven distance from the start, whatever direction it lies in. Each closed intersection has its final distance; its streets are relaxed so that neighbours reached more cheaply get a new distance and a new parent.

With no idea where the goal is, the search fills a disc of the map that grows until the goal falls inside it. On a city grid that means closing several times more intersections than A*, yet the route is identical: both are exact, only the effort differs.

02

The four stages

1
placetwo intersections about n × 100 m apart
2
popthe lowest distance so far
3
relaxshorter way to a neighbour: new distance, new parent
4
routefollow parents back along the streets
03

Complexity

best
O(d)the goal next door
average
O(E log V)a disc of radius the route length
worst
O(E log V)the whole map before a far goal
space
O(V)distances, parents and the open set
04

Versus its siblings

INTERSECTIONS EXPANDED · CASCAVEL, 3.2 km ROUTE
a*
537
dijkstra
2,045
bfs
2,303
same start and goal (seed 7, route 30) · 3 949 intersections in the map
05

Pseudocode

ROUTE(map, start, goal)
  open ← {start}; distance[start] ← 0
  while open not empty
    current ← the open intersection with the lowest distance
    if current = goal: return the route via parent
    for each street leaving current, to neighbour
      if distance[current] + street.metres < distance[neighbour]: update it, parent[neighbour] ← current, add neighbour to open
06

When to use

Any road, rail or pipe network with lengths on the segments: GPS routing, logistics, network packets.
Rerun on a longer route (the slider) to watch the gap between the three searches open up.
07

Pitfalls

One source, every destination: if you need the whole distance table, Dijkstra is the right tool and A* is not.
Negative lengths do not exist on roads, but they do on graphs with credits; then use Bellman–Ford.
Popping a stale entry must be skipped, or an intersection is expanded twice with a wrong distance.
08

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.

Back to Pathfinding