Pathfinding and centrality algorithms

This section documents the current Neo4j 2026.x calendar-versioned line — Neo4j moved from semantic to calendar versioning (YYYY.MM) in 2025, and the same line applies to the Graph Data Science library — as published at the Neo4j documentation, which is the reference these pages are written and verified against. No specific monthly patch is pinned. Some areas (Aura’s internal infrastructure, the Raft consensus implementation details, and the GDS Pregel API’s low-level internals) are linked, not documented in depth.

This content was generated with the assistance of AI and should be verified against the official documentation before being relied on in production, as Neo4j iterates quickly.

This section’s bibliography lists the reference material consulted while preparing these pages.

Once a graph is projected into memory (see Graph Data Science Fundamentals), two families of GDS algorithms answer most practical graph questions: pathfinding finds routes between specific nodes, and centrality ranks every node by some notion of importance. Both families share the same stream / write / mutate execution modes; the examples below use stream to return results without persisting them.

Pathfinding algorithms

Pathfinding algorithms need weighted relationships to be meaningful, so this section uses a small :Location / :ROAD road network rather than the :Person / :Movie domain — distances between places map naturally onto relationship weights, which acted-in credits do not.

CREATE (a:Location {name: 'Turin'})
CREATE (b:Location {name: 'Milan'})
CREATE (c:Location {name: 'Genoa'})
CREATE (d:Location {name: 'Bologna'})
CREATE (e:Location {name: 'Florence'})
CREATE (a)-[:ROAD {distance: 140}]->(b)
CREATE (a)-[:ROAD {distance: 170}]->(c)
CREATE (b)-[:ROAD {distance: 210}]->(d)
CREATE (c)-[:ROAD {distance: 300}]->(d)
CREATE (d)-[:ROAD {distance: 100}]->(e)

CALL gds.graph.project(
  'roads',
  'Location',
  {ROAD: {orientation: 'UNDIRECTED', properties: 'distance'}}
)

Dijkstra: single-pair and single-source shortest path

Dijkstra’s algorithm finds the lowest-total-weight path from one source node, either to a single target or to every reachable node, and is the default choice whenever all relationship weights are non-negative (Dijkstra Source-Target).

MATCH (source:Location {name: 'Turin'}), (target:Location {name: 'Florence'})
CALL gds.shortestPath.dijkstra.stream('roads', {
  sourceNode: source,
  targetNode: target,
  relationshipWeightProperty: 'distance'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs
RETURN
  gds.util.asNode(sourceNode).name AS from,
  gds.util.asNode(targetNode).name AS to,
  totalCost,
  [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS route

A*: shortest path guided by a spatial heuristic

A* refines Dijkstra with a heuristic — typically great-circle distance between latitude/longitude point properties — that steers the search toward the target instead of expanding outward evenly, reaching the same optimal answer while visiting fewer nodes on geographically spread graphs (A* Shortest Path).

MATCH (source:Location {name: 'Turin'}), (target:Location {name: 'Florence'})
CALL gds.shortestPath.astar.stream('roads', {
  sourceNode: source,
  targetNode: target,
  relationshipWeightProperty: 'distance',
  latitudeProperty: 'latitude',
  longitudeProperty: 'longitude'
})
YIELD sourceNode, targetNode, totalCost
RETURN
  gds.util.asNode(sourceNode).name AS from,
  gds.util.asNode(targetNode).name AS to,
  totalCost

Yen’s algorithm: k-shortest paths

Yen’s algorithm returns not just the single best path but the k best loopless paths in increasing order of cost — useful whenever the true requirement is a ranked set of alternatives rather than one route, such as offering a traveler a primary route plus fallbacks (Yen’s Algorithm).

MATCH (source:Location {name: 'Turin'}), (target:Location {name: 'Florence'})
CALL gds.shortestPath.yens.stream('roads', {
  sourceNode: source,
  targetNode: target,
  relationshipWeightProperty: 'distance',
  k: 3
})
YIELD index, totalCost, nodeIds
RETURN index, totalCost,
  [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS route
ORDER BY index

These three cover the common cases: Dijkstra for a plain weighted shortest path, A* when nodes carry real coordinates worth exploiting, and Yen’s when several ranked alternatives are needed instead of just the best one. All three, and the wider pathfinding family, are indexed at GDS Algorithms.

Centrality algorithms

Centrality algorithms score every node in a projected graph by some notion of "importance" — how connected it is, how much traffic flows through it, or how close it sits to everything else. They run over the whole graph rather than between two chosen nodes, and the examples below switch back to a :Person ACTED_IN style graph, projected undirected for the connectivity-based measures.

CALL gds.graph.project(
  'people',
  'Person',
  {ACTED_IN: {orientation: 'UNDIRECTED'}}
)
Algorithm What it measures Typical use

Degree

How many relationships a node has (in, out, or both).

Quick popularity/activity signal; a cheap first pass before running heavier measures.

PageRank

How much influence flows into a node, weighted by the influence of the nodes pointing at it.

Ranking overall importance in a directed graph, e.g. influential accounts or authoritative pages.

Betweenness

How often a node sits on the shortest path between other pairs of nodes.

Finding bridges/brokers whose removal would fragment the graph or lengthen many routes.

Closeness

How short a node’s paths are, on average, to every other node.

Finding nodes that can reach the rest of the graph fastest, e.g. a good broadcast or facility location.

Eigenvector

Like PageRank, but a node’s score depends purely on the score of its neighbors, with no damping/random-jump term.

Ranking importance in graphs without a natural directed "vote", e.g. undirected social or collaboration graphs.

Degree centrality

CALL gds.degree.stream('people')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS person, score
ORDER BY score DESC
LIMIT 10

PageRank and Personalized PageRank

Plain PageRank scores every node from the whole graph’s link structure (PageRank). Passing sourceNodes turns it into Personalized PageRank: the random walk always resets back to that source set instead of to any node in the graph, so the score answers "important relative to these specific starting nodes" rather than "important overall" — for example, ranking movies by relevance to one actor’s neighborhood rather than globally.

CALL gds.pageRank.stream('people', {
  maxIterations: 20,
  dampingFactor: 0.85
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS person, score
ORDER BY score DESC
LIMIT 10
MATCH (ada:Person {name: 'Ada'})
CALL gds.pageRank.stream('people', {
  sourceNodes: [ada],
  maxIterations: 20,
  dampingFactor: 0.85
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS person, score
ORDER BY score DESC
LIMIT 10

Betweenness centrality

CALL gds.betweenness.stream('people')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS person, score
ORDER BY score DESC
LIMIT 10

Closeness centrality

CALL gds.closeness.stream('people')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS person, score
ORDER BY score DESC
LIMIT 10

Eigenvector centrality

CALL gds.eigenvector.stream('people', {
  maxIterations: 20
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS person, score
ORDER BY score DESC
LIMIT 10

The full centrality family — including weighted and relationship-orientation variants of each algorithm above — is indexed at GDS Algorithms.

Where these algorithms are applied

Both families depend on the projection and configuration groundwork covered in Graph Data Science Fundamentals. For worked, end-to-end scenarios that combine them with real business questions — routing and logistics optimization built on weighted shortest paths, and fraud-ring detection built on centrality and community structure — see Use Cases and Algorithms in Practice.