GraphGuru | Geospatial Graphs in Neo4j: Point Indexes, Distance Queries, and Routing with Dijkstra and A*

Every logistics, field-service, telecom, and store-network project we take on eventually asks the same two questions: what is near this point? and what is the cheapest path between these two points? Neo4j answers both without a separate geospatial stack — the POINT type is native, point indexes are first-class, and Graph Data Science ships weighted shortest-path algorithms that run over the same graph. This tutorial builds a small road network, indexes it spatially, and routes over it with Dijkstra, A*, and Yen's k-shortest paths.

Everything below runs on Neo4j 2025.x / 2026.x (Cypher 25) with the Graph Data Science plugin installed. If you need an instance, the Docker setup from our earlier tutorial works — just add GDS to NEO4J_PLUGINS.

The `POINT` type in 60 seconds

Neo4j has two spatial coordinate reference systems that matter:

WGS-84 (srid: 4326 for 2D, 4979 for 3D) — latitude/longitude on a globe. Distances come back in metres, computed with the haversine formula.
Cartesian (srid: 7203 / 9157) — a flat plane, distances in whatever unit you put in. Use it for floor plans, warehouse layouts, and game maps.

Do not mix them. point.distance() between points of different CRS returns null, silently, and that null will propagate into a routing cost and give you a route with no length rather than an error.

RETURN point({latitude: 51.5072, longitude: -0.1276}) AS london,
       point({x: 12.0, y: 4.5}) AS floorplan;

Store the location as a single point property; do not keep lat and lon as separate floats and rebuild the point at query time, because a point index cannot help you then.

Step 1 — model and load the network

A routing graph is the one case where the relationships carry most of the data. Intersections become nodes; road segments become relationships with a length and a travel time.

CREATE CONSTRAINT junction_id IF NOT EXISTS
FOR (j:Junction) REQUIRE j.id IS UNIQUE;

CREATE POINT INDEX junction_location IF NOT EXISTS
FOR (j:Junction) ON (j.location);

Load some junctions. In a real project this comes from OpenStreetMap or your own network data; here is enough to work with:

UNWIND [
  {id: 'A', lat: 51.5072, lon: -0.1276},
  {id: 'B', lat: 51.5155, lon: -0.1410},
  {id: 'C', lat: 51.5194, lon: -0.1270},
  {id: 'D', lat: 51.5246, lon: -0.1340},
  {id: 'E', lat: 51.5310, lon: -0.1230}
] AS row
MERGE (j:Junction {id: row.id})
SET j.location = point({latitude: row.lat, longitude: row.lon});

Now create the segments and let Cypher compute their geometric length, so the cost property can never drift out of sync with the geometry:

UNWIND [
  {from: 'A', to: 'B', kph: 30.0},
  {from: 'B', to: 'C', kph: 50.0},
  {from: 'A', to: 'C', kph: 20.0},
  {from: 'C', to: 'D', kph: 50.0},
  {from: 'B', to: 'D', kph: 30.0},
  {from: 'D', to: 'E', kph: 60.0},
  {from: 'C', to: 'E', kph: 25.0}
] AS row
MATCH (a:Junction {id: row.from}), (b:Junction {id: row.to})
MERGE (a)-[r:ROAD]->(b)
SET r.metres  = point.distance(a.location, b.location),
    r.seconds = point.distance(a.location, b.location) / (row.kph / 3.6);

Two modelling notes we make on nearly every review:

Direction is data. A one-way street is a single ROAD relationship; a two-way street is two. Do not fake bidirectionality by matching undirected at query time — GDS treats the projection's orientation as truth, and your one-way rules evaporate.
Cost is a property, not a formula. Store seconds (or metres, or a toll-weighted cost) on the relationship. The algorithms need a single numeric weight; computing it inside the traversal is not an option.

Step 2 — spatial lookups: bounding box, then distance

The classic "find the nearest junction to where the driver is standing" query. The point index accelerates range predicates, so write the bounding box first and let the distance filter refine it:

WITH point({latitude: 51.5180, longitude: -0.1300}) AS me
MATCH (j:Junction)
WHERE point.withinBBox(
        j.location,
        point({latitude: 51.5100, longitude: -0.1400}),
        point({latitude: 51.5260, longitude: -0.1200}))
  AND point.distance(j.location, me) < 800
RETURN j.id, round(point.distance(j.location, me)) AS metres
ORDER BY metres
LIMIT 5;

point.withinBBox is index-backed. A bare point.distance(...) < 800 is not — on a large graph it degrades to a scan of every node with a location. PROFILE this query and confirm you see a NodeIndexSeekByRange rather than a NodeByLabelScan; our PROFILE plan tutorial covers how to read that output.

A rough rule for sizing the box: one degree of latitude is about 111 km everywhere; one degree of longitude is about 111 × cos(latitude) km. At London's latitude, 800 m is roughly 0.0072° of latitude and 0.0116° of longitude.

Step 3 — project the graph for GDS

GDS runs on an in-memory projection. Project the junctions, the roads, and the cost property:

MATCH (source:Junction)-[r:ROAD]->(target:Junction)
RETURN gds.graph.project(
  'roads',
  source,
  target,
  {
    sourceNodeProperties: {lat: source.location.latitude, lon: source.location.longitude},
    targetNodeProperties: {lat: target.location.latitude, lon: target.location.longitude},
    relationshipProperties: {seconds: r.seconds}
  }
);

The Cypher projection (gds.graph.project used as a function) is the current form. It matters here because A* needs latitude and longitude as plain node properties, and the function lets you compute them from the point during projection.

Step 4 — Dijkstra, A*, and Yen's k-shortest paths

Dijkstra source-target — the default choice: exact, no tuning.

MATCH (a:Junction {id: 'A'}), (e:Junction {id: 'E'})
CALL gds.shortestPath.dijkstra.stream('roads', {
  sourceNode: a,
  targetNode: e,
  relationshipWeightProperty: 'seconds'
})
YIELD totalCost, nodeIds
RETURN round(totalCost) AS seconds,
       [id IN nodeIds | gds.util.asNode(id).id] AS route;

A* — Dijkstra plus a geographic heuristic. It expands far fewer nodes on a large road network because it prefers candidates that are physically closer to the destination:

MATCH (a:Junction {id: 'A'}), (e:Junction {id: 'E'})
CALL gds.shortestPath.astar.stream('roads', {
  sourceNode: a,
  targetNode: e,
  latitudeProperty: 'lat',
  longitudeProperty: 'lon',
  relationshipWeightProperty: 'seconds'
})
YIELD totalCost, nodeIds
RETURN round(totalCost) AS seconds,
       [id IN nodeIds | gds.util.asNode(id).id] AS route;

A* only returns the true optimum if its heuristic never overestimates the remaining cost. The built-in heuristic is straight-line distance, which is admissible when your weight is distance in metres. If your weight is travel time, the comparable heuristic is distance divided by the network's maximum speed — so either weight by distance, or scale your time weights consistently, or accept that A* has become a fast approximation. This is the most common bug we find in hand-rolled Neo4j routing code: a distance heuristic over a time-weighted graph, quietly returning second-best routes.

Yen's k-shortest paths — when the business wants alternatives ("show three routes"), or you need a fallback when the first route is blocked:

MATCH (a:Junction {id: 'A'}), (e:Junction {id: 'E'})
CALL gds.shortestPath.yens.stream('roads', {
  sourceNode: a,
  targetNode: e,
  k: 3,
  relationshipWeightProperty: 'seconds'
})
YIELD index, totalCost, nodeIds
RETURN index, round(totalCost) AS seconds,
       [id IN nodeIds | gds.util.asNode(id).id] AS route
ORDER BY index;

Single-source Dijkstra answers a different and very useful question — everything reachable within a cost budget — which is how you build a service-area or isochrone map:

MATCH (depot:Junction {id: 'A'})
CALL gds.allShortestPaths.dijkstra.stream('roads', {
  sourceNode: depot,
  relationshipWeightProperty: 'seconds'
})
YIELD targetNode, totalCost
WITH gds.util.asNode(targetNode) AS j, totalCost
WHERE totalCost <= 600
RETURN j.id, round(totalCost) AS seconds
ORDER BY seconds;

Step 5 — writing routes back, and refreshing projections

For a route computed on every request, streaming is right. For routes you compute once and serve many times — depot-to-store, tower-to-subscriber — use write mode and persist the path:

MATCH (a:Junction {id: 'A'}), (e:Junction {id: 'E'})
CALL gds.shortestPath.dijkstra.write('roads', {
  sourceNode: a, targetNode: e,
  relationshipWeightProperty: 'seconds',
  writeRelationshipType: 'ROUTE',
  writeNodeIds: true, writeCosts: true
})
YIELD relationshipsWritten
RETURN relationshipsWritten;

Drop the projection when the job is done — it holds heap:

CALL gds.graph.drop('roads');

Projections are snapshots. If your costs change with live traffic or closures, either re-project on a schedule (cheap — seconds for a city-scale network) or keep one projection per time band, rush hour and off-peak, and route against the right one. Neo4j CDC is a clean trigger for "the network changed, refresh the projection".

Cypher-only routing, without GDS

If you cannot install GDS, SHORTEST in Cypher 25 gets you hop-count paths, and quantified path patterns let you bound the search:

MATCH p = SHORTEST 1 (a:Junction {id: 'A'})-[:ROAD]->{1,10}(e:Junction {id: 'E'})
RETURN [n IN nodes(p) | n.id] AS route,
       reduce(s = 0.0, r IN relationships(p) | s + r.seconds) AS seconds;

Read that carefully: it is the shortest path by hop count, which then reports its cost. That is not the cheapest path. Where the weight matters — time, distance, toll, signal loss — use Dijkstra or A*.

Performance checklist

A point index on every location property you filter on, with bounding-box predicates so the index is actually used.
Degree matters. A junction with hundreds of segments is a supernode for the router; see our notes on finding and refactoring supernodes.
Contract long chains. Runs of degree-2 junctions between real intersections collapse into a single relationship with the summed cost. On real OSM extracts this routinely removes most of the nodes and is the largest single routing speed-up available.
Size the projection. gds.graph.list reports its memory; check that against your heap before projecting a national network. Our memory sizing guide covers the heap and page-cache split.
Match the A* heuristic to the weight. Repeated because it is that common.

Where this goes next

Spatial graphs get interesting when the routing layer meets the rest of the domain: technicians with skills and shift windows, vehicles with capacity, orders with time windows. At that point you are doing constraint optimisation with the graph as a distance oracle, and Neo4j's job is to answer "cost from here to there, respecting the network" fast enough to sit inside a solver loop.

If you are building that — or your spatial queries are scanning when they should be seeking — our Neo4j consultants have shipped routing and service-area systems on Neo4j and can review a model in a few days. Get in touch.

Geospatial Graphs in Neo4j: Point Indexes, Distance Queries, and Routing with Dijkstra and A*

The POINT type in 60 seconds