Weighted Dijkstra Routing with Neo4j GDS

When a route query needs weighted shortest paths at scale — a single source to one target, or a source to every reachable node as a cost surface — the hand-written traversal that round-trips per expanded node stops being the right tool. The Graph Data Science library runs a parallel, in-database Dijkstra over a projected in-memory graph, so the entire search happens on the server and only the result crosses the wire. The catch is the projection lifecycle: a projected graph is a named, heap-resident object that outlives the query, and getting its creation, reuse, and disposal wrong is how a routing service leaks memory until GDS refuses to project anything at all. This page runs gds.shortestPath.dijkstra and gds.allShortestPaths.dijkstra from async Python end to end — project a weighted subgraph, stream results, drop the projection — and contrasts it with the hand-written A* implementation. It is a focused companion to the Routing Algorithms in Python decision guide.

Prerequisites & Versions

The GDS plugin must be installed on the server; the client side is the plain async driver calling CALL gds.* procedures, which keeps the whole flow in one async transaction model.

Requirement Minimum version Note
Python 3.10+ async/await, f-strings
Neo4j 5.13+ Native point, unique constraint on the node id
GDS plugin 2.6+ gds.graph.project, gds.shortestPath.dijkstra
neo4j (driver) 5.x AsyncGraphDatabase 
pip install "neo4j>=5.18"

The graph carries a scalar routing weight on each relationship — here drive_s, travel time in seconds — kept distinct from raw length, following the node and edge spatial mapping conventions. A unique constraint on the node id lets the anchor lookup seek the source and target before projection.

Core Concept & Mechanism

GDS does not run over your stored graph. It runs over a named projection: a compressed, in-memory copy of a chosen node and relationship subset, materialised once and referenced by name across many algorithm calls. The relationship weight the algorithm minimises must be projected as a relationship property — Dijkstra reads it from the in-memory structure, never from the stored relationship. The lifecycle is always the same three moves: project the subgraph, run one or more algorithms against the named graph, drop the projection to reclaim the heap.

Two Dijkstra procedures cover the routing shapes:

  • gds.shortestPath.dijkstra — one source to one target, returning the single optimal path and its totalCost.
  • gds.allShortestPaths.dijkstra — one source to every reachable node, returning a cost surface: the optimal cost from the source to all targets in a single pass. This is the one-to-many case where a heuristic would have no single goal to bias toward, so Dijkstra, not A*, is the correct algorithm.
From stored graph to a named GDS projection to a Dijkstra source-to-targets cost surface Three stages left to right. First, the stored property graph of intersections and weighted segments. An arrow labelled gds.graph.project leads to the second stage, a named in-memory projection holding the same topology plus the drive_s weight. An arrow labelled dijkstra leads to the third stage, a cost surface: a source node radiates concentric cost rings, and three target nodes are annotated with their optimal costs from the source. Dropping the projection afterwards reclaims the heap. Stored graph :Intersection -[:SEGMENT {drive_s}]-> project Named projection 'sf_road' in-memory copy weight: drive_s heap-resident until dropped dijkstra Cost surface S 210s 330s 540s optimal cost S → every target

Implementation

The coroutine below projects a weighted subgraph, runs a point-to-point Dijkstra, then a one-to-many cost surface, and drops the projection in a finally block so a mid-query exception can never orphan the in-memory graph. The example routes across the San Francisco Bay Area.

import asyncio
from neo4j import AsyncDriver, AsyncGraphDatabase

GRAPH_NAME = "sf_road"

PROJECT = """
CALL gds.graph.project(
  $graph,
  'Intersection',
  { SEGMENT: { properties: 'drive_s' } }
)
YIELD graphName, nodeCount, relationshipCount
RETURN graphName, nodeCount, relationshipCount
"""

POINT_TO_POINT = """
MATCH (src:Intersection {id: $src}), (dst:Intersection {id: $dst})
CALL gds.shortestPath.dijkstra.stream($graph, {
  sourceNode: src,
  targetNode: dst,
  relationshipWeightProperty: 'drive_s'
})
YIELD totalCost, nodeIds
RETURN totalCost AS cost_s,
       [nid IN nodeIds | gds.util.asNode(nid).id] AS route
"""

ONE_TO_MANY = """
MATCH (src:Intersection {id: $src})
CALL gds.allShortestPaths.dijkstra.stream($graph, {
  sourceNode: src,
  relationshipWeightProperty: 'drive_s'
})
YIELD targetNode, totalCost
RETURN gds.util.asNode(targetNode).id AS target_id, totalCost AS cost_s
ORDER BY cost_s ASC
LIMIT 25
"""

DROP = "CALL gds.graph.drop($graph, false) YIELD graphName RETURN graphName"


async def project_if_absent(session, graph: str) -> None:
    exists = await session.run("RETURN gds.graph.exists($graph) AS ok", graph=graph)
    if (await exists.single())["ok"]:
        return
    await (await session.run(PROJECT, graph=graph)).consume()


async def route_with_gds(driver: AsyncDriver, src: str, dst: str) -> dict:
    async with driver.session(database="neo4j") as session:
        await project_if_absent(session, GRAPH_NAME)
        try:
            p2p = await (await session.run(
                POINT_TO_POINT, graph=GRAPH_NAME, src=src, dst=dst)).single()
            surface = [rec.data() async for rec in await session.run(
                ONE_TO_MANY, graph=GRAPH_NAME, src=src)]
            return {
                "cost_s": p2p["cost_s"] if p2p else None,
                "route": p2p["route"] if p2p else [],
                "nearest_targets": surface,
            }
        finally:
            await (await session.run(DROP, graph=GRAPH_NAME)).consume()


async def main():
    driver = AsyncGraphDatabase.driver(
        "neo4j://localhost:7687", auth=("neo4j", "secure-password"),
        max_connection_pool_size=20, connection_acquisition_timeout=15.0,
    )
    try:
        # Ferry Building -> Oracle Park, San Francisco
        result = await route_with_gds(driver, "I-sf-embarcadero", "I-sf-mission-bay")
        if result["cost_s"] is not None:
            print(f"Fastest path: {result['cost_s'] / 60:.1f} min, "
                  f"{len(result['route'])} intersections")
        print(f"Reachable-target sample: {len(result['nearest_targets'])} rows")
    finally:
        await driver.close()


if __name__ == "__main__":
    asyncio.run(main())

How It Works

  • Projection is idempotent by guard, not by default. gds.graph.project errors if a graph of that name already exists, so project_if_absent checks gds.graph.exists first. In a long-lived service you typically project once at startup for a stable graph and skip the per-request project/drop cycle entirely — reproject only when the topology or weights change.
  • The weight is a projected property. { SEGMENT: { properties: 'drive_s' } } copies drive_s into the in-memory relationships, and relationshipWeightProperty: 'drive_s' tells Dijkstra to minimise it. Omit either half and the algorithm silently treats every edge as weight 1.0, returning a hop-optimal path dressed up as a cost-optimal one.
  • Streaming keeps results off the server heap. The .stream mode yields rows straight to the driver rather than writing back to the graph, and the async async for consumes them incrementally. gds.util.asNode(nid).id translates the internal node id GDS returns back into your application id.
  • The projection is dropped in finally. gds.graph.drop($graph, false) — the false means “do not fail if absent” — runs whether or not the query succeeded, so an exception cannot leave a multi-gigabyte projection stranded on the heap.

Where the hand-written A* search pays one network round trip per expanded node and lets you shape the cost function in Python per request, GDS pays a one-time projection cost and then runs the entire search server-side in parallel. A* wins on a single point-to-point query with a custom or dynamic cost function; GDS wins decisively on one-to-many cost surfaces and on high query volume against a stable graph, where the projection amortises. The measured crossover is laid out in Neo4j GDS vs Custom Cypher Routing.

Common Failure Patterns

1. Projection memory blowup. A projection is a heap object sized to its node and relationship count plus every projected property. Projecting the entire graph when a query only needs one metro area can exhaust GDS’s heap and make the next project call fail outright. Project a subgraph, not the world — filter with a node label or a Cypher projection scoped to a region — and monitor gds.graph.list for projections that should have been dropped.

// Scope the projection to a region instead of the whole graph
MATCH (n:Intersection)-[r:SEGMENT]->(m:Intersection)
WHERE n.metro = $metro AND m.metro = $metro
RETURN gds.graph.project($graph, n, m, { relationshipProperties: r { .drive_s } })

2. Stale projection after a write. The projection is a snapshot. Update drive_s on the stored graph — a traffic re-weighting, a closed road — and every subsequent Dijkstra over the old projection returns costs for the previous state, with no error to signal it. Treat the projection as a cache keyed on a topology/weight version and drop-and-reproject on any write that touches routing weights.

async def refresh_projection(session, graph: str) -> None:
    await session.run(DROP, graph=graph)          # drop stale snapshot
    await session.run(PROJECT, graph=graph)       # reproject current weights

3. Missing relationship weight property. If relationshipWeightProperty names a property that was not projected (or is misspelled), GDS does not error — it falls back to treating all relationships as unit-weight, so Dijkstra returns the hop-optimal path and the total cost is a count of edges, not seconds. The tell is a totalCost that is a small integer. Always assert the property is in the projection and that returned costs are in the expected unit and magnitude.

Performance Notes

The cost model has two distinct terms: a one-time projection cost proportional to the projected node and relationship count, and a per-query Dijkstra cost. Amortised over $q$ queries against one projection, the effective per-query cost is

$$C_{\text{eff}} = \frac{C_{\text{project}}}{q} + C_{\text{query}},$$

so the project/drop-per-request pattern shown above — chosen here for a self-contained example — is the worst case: it pays $C_{\text{project}}$ on every single query ($q = 1$). In production, project once and reuse across thousands of queries so $C_{\text{project}}/q$ vanishes and only the parallel Dijkstra cost remains. The one-to-many allShortestPaths call is where GDS earns its keep: computing a full cost surface from one source is a single Dijkstra sweep, whereas the hand-written approach would need one search per target.

Size the projection against available heap before serving traffic — a projection that spills is worse than no projection. When a query only ever touches a bounded corridor, a distance-filtered subgraph projection keeps the in-memory footprint proportional to the region you actually route within, not the whole network.

This guide is part of Routing Algorithms in Python, within the Network Routing Algorithms in Python pillar.

For authoritative procedure signatures and configuration, consult the Neo4j GDS Dijkstra source-target documentation and the GDS graph projection reference.

Siblings