Pathfinding and Spanning/Reachability Algorithms: When GDS Beats Transactional Cypher

Learning outcomes

1. AtlasMart problem: route planning is not the same as graph matching

AtlasMart operations wants the cheapest transfer route between fulfillment locations, a reachability check during an outage, and a minimum-cost connection structure for a planning exercise. Those are three distinct graph questions. A generic variable-length pattern can express connectivity, but GDS provides specialized algorithms whose assumptions and output are explicit.

The key boundary: GDS does not automatically “beat Cypher.” Projection creation has a cost. For one small transactional request, a Cypher shortest-path expression may be simpler. GDS becomes attractive when the analytical graph is reused, the algorithm family is specialized, or many path computations justify the in-memory representation.

2. Path/reachability family map

3. Build a five-location route fixture with a manual shortest path

UNWIND [
  ['CH24-L-A','Warehouse A'], ['CH24-L-B','Hub B'],
  ['CH24-L-C','Hub C'], ['CH24-L-D','Store D'], ['CH24-L-E','Store E']
] AS row
CREATE (:Location:CH24Location {locationId:row[0], name:row[1], chapter24:true});

MATCH (a:Location {locationId:'CH24-L-A'}), (b:Location {locationId:'CH24-L-B'}),
      (c:Location {locationId:'CH24-L-C'}), (d:Location {locationId:'CH24-L-D'}),
      (e:Location {locationId:'CH24-L-E'})
CREATE (a)-[:ROUTE_TO {minutes:4.0}]->(b),
       (a)-[:ROUTE_TO {minutes:7.0}]->(c),
       (b)-[:ROUTE_TO {minutes:3.0}]->(c),
       (b)-[:ROUTE_TO {minutes:6.0}]->(d),
       (c)-[:ROUTE_TO {minutes:2.0}]->(d),
       (d)-[:ROUTE_TO {minutes:2.0}]->(e),
       (c)-[:ROUTE_TO {minutes:9.0}]->(e);

CALL gds.graph.project(
  'atlas-ch24-routes',
  'CH24Location',
  {ROUTE_TO:{properties:['minutes']}}
) YIELD graphName, nodeCount, relationshipCount;

Manual route A→E: A→B→C→D→E costs 4+3+2+2=11. A→C→D→E also costs 7+2+2=11. A→B→D→E costs 12; A→C→E costs 16. Therefore an 11-minute path is the deterministic minimum, but tie ordering among equal-cost shortest paths is an implementation/output detail to observe rather than hard-code.

4. Dijkstra: cost semantics dominate the result

MATCH (source:Location {locationId:'CH24-L-A'}),
      (target:Location {locationId:'CH24-L-E'})
CALL gds.shortestPath.dijkstra.stream('atlas-ch24-routes', {
  sourceNode:source,
  targetNodes:[target],
  relationshipWeightProperty:'minutes'
})
YIELD totalCost, nodeIds, costs
RETURN totalCost,
       [nodeId IN nodeIds | gds.util.asNode(nodeId).locationId] AS route,
       costs;

5. BFS/DFS answer reachability/order questions, not weighted optimum

MATCH (source:Location {locationId:'CH24-L-A'}),
      (target:Location {locationId:'CH24-L-D'})
CALL gds.bfs.stream('atlas-ch24-routes', {
  sourceNode:source,
  targetNodes:[target],
  maxDepth:3
}) YIELD nodeIds
RETURN [id IN nodeIds | gds.util.asNode(id).locationId] AS visitedInBfsOrder;

MATCH (source:Location {locationId:'CH24-L-A'})
CALL gds.dfs.stream('atlas-ch24-routes', {
  sourceNode:source,
  maxDepth:3
}) YIELD nodeIds
RETURN [id IN nodeIds | gds.util.asNode(id).locationId] AS visitedInDfsOrder;

BFS visits by increasing hop distance; DFS pursues a branch before backtracking. Neither is a substitute for Dijkstra when minutes is the optimization objective.

6. Spanning is a network-structure question

MATCH (source:Location {locationId:'CH24-L-A'})
CALL gds.spanningTree.stream.estimate('atlas-ch24-routes', {
  sourceNode: source,
  relationshipWeightProperty:'minutes'
})
YIELD nodeCount, relationshipCount, requiredMemory
RETURN *;

MATCH (source:Location {locationId:'CH24-L-A'})
CALL gds.spanningTree.stream('atlas-ch24-routes', {
  sourceNode:source,
  relationshipWeightProperty:'minutes'
})
YIELD nodeId, parentId, weight
RETURN gds.util.asNode(nodeId).locationId AS node,
       gds.util.asNode(parentId).locationId AS parent,
       weight
ORDER BY node;

7. When GDS versus transactional Cypher?

Measure end-to-end latency including projection/rebuild time, not only the algorithm’s computeMillis. “GDS is faster” without workload shape and refresh cost is vendor folklore.

8. Deliberately wrong: use “strength” as Dijkstra cost

If strength=10 means “very strong connection,” Dijkstra interprets 10 as more expensive than 2. The algorithm can be technically correct and business-semantically wrong. Repair by defining a non-negative additive cost such as minutes, distance, risk penalty, or a carefully justified inverse transform. Validate units and zero/negative edge cases before running.

Production judgment and bridge

The final lesson turns all of Chapter 24 into a decision discipline: algorithm choice starts with the business/analytical question and ends with falsifiable assumptions, baselines, stability evidence, and restrained interpretation.

Summary and next step

Pathfinding and Spanning/Reachability Algorithms: When GDS Beats Transactional Cypher is useful only when its assumptions and observed evidence stay attached to the decision. The examples above establish a reproducible mechanism and boundary; they do not turn one lab result into a universal production rule.

Next, continue to Choose an Algorithm from the Decision Question, Validate Assumptions, and Interpret Results Without Overclaiming. Carry forward the verified assumptions, fixture state, version/edition boundaries, and measurements from this lesson instead of treating the next topic as an isolated recipe.

Authoritative references

• GDS Manual v2026.07 — Current Graph Data Science manual and release baseline.
• GDS supported Neo4j versions — Compatibility matrix mapping Neo4j 2026.07 to GDS 2026.07.
• GDS editions — Community includes all algorithms but caps concurrency at four CPU cores and the model catalog at three models; Enterprise adds operational capabilities.
• Algorithm syntax and execution modes — stream/stats/mutate/write/estimate semantics and common algorithm configuration.
• Memory estimation — Estimate memory before allocating algorithm working state.
• Centrality algorithms — Current centrality family and quality tiers.
• Degree Centrality — Degree semantics and weighted/directed behavior.
• PageRank — PageRank iteration, damping, weights, and execution modes.
• Betweenness Centrality — Exact/sampled betweenness, samplingSize/samplingSeed, memory and concurrency tradeoffs.
• Eigenvector Centrality — Transitive influence and power-iteration semantics.
• Louvain — Modularity, levels, tolerance, seeding and execution modes.
• Leiden — Community detection with gamma, theta, randomSeed and connectivity refinement.
• Label Propagation — Fast topology-driven community detection, optional weights and seeds.
• Node Similarity — Structural neighborhood similarity with Jaccard, Overlap, or Cosine.
• K-Nearest Neighbors — Property-based approximate KNN and supported metrics.
• Path finding algorithms — Current shortest path, traversal, spanning, and flow families.
• Dijkstra Source-Target — Positive-cost shortest path semantics; sourceNode/targetNodes current syntax.
• Breadth First Search — Reachability traversal, targets, maxDepth, and stream/mutate modes.
• Graph algorithm operations reference — Current procedure/function names including spanningTree and similarity functions.
• Neo4j current versions — Current Neo4j database release and 5.26 LTS line.