Paths and shortest-path queries

Wiki / Cypher query language

On this page

Graph algorithms

Two flavours: procedure-based (weighted, on the live graph) and Cypher path search (unweighted, in a MATCH).

Procedures (weighted)

gdb.dijkstra, gdb.astar, gdb.pageRank, gdb.degree — full signatures in Live graph algorithms. For repeated queries over a projected graph, use projected pathfinding: Dijkstra, A*, Yen and Hourglass.

CALL gdb.dijkstra(0, 42, 'ROAD', 'km', 'OUT') YIELD nodeIds, totalCost
RETURN nodeIds, totalCost;

CALL gdb.pageRank('LINKS', 30, 0.85) YIELD nodeId, score
RETURN nodeId, score ORDER BY score DESC LIMIT 10;

shortestPath / allShortestPaths (unweighted, in MATCH)

MATCH (a:Person {name: 'Ada'}), (b:Person {name: 'Zoe'})
MATCH p = shortestPath((a)-[:KNOWS*]-(b))
RETURN length(p), [n IN nodes(p) | n.name];

MATCH (a:Person {name: 'Ada'}), (b:Person {name: 'Zoe'})
MATCH p = allShortestPaths((a)-[:KNOWS*]-(b))
RETURN p;

These do a breadth-first search and return the shortest (or all equally-shortest) paths by hop count.

From version 2.4.2 the search visits each node once, so its time follows the number of nodes it reaches and not the number of paths between the two ends. A start node is searched once for all of its end nodes.

Data-science similarity functions

Pairwise vector similarity functions (gds.similarity.*, vector.similarity.*) are documented in Pairwise similarity functions.

MATCH (a:Doc {id: 1}), (b:Doc)
WHERE b.id <> 1
RETURN b.id, gds.similarity.cosine(a.embedding, b.embedding) AS sim
ORDER BY sim DESC LIMIT 5;

Quantified path patterns

A parenthesised pattern followed by a quantifier is repeated, each repetition starting on the node the previous one ended on:

// one to three NEXT hops from a station
MATCH (a:Station {name: 'Denmark Hill'}) ((x)-[r:NEXT]->(y)){1,3} (b)
RETURN b.name, [e IN r | e.time] AS legs;

// every hop must stay cheap; any number of hops
MATCH (a:Station {name: 'Denmark Hill'}) ((x)-[r:NEXT]->(y) WHERE r.time < 5)+ (b:Station)
RETURN b.name;

Quantifiers are {n}, {n,m}, {n,}, {,m}, + (one or more) and * (zero or more). Inside the parentheses a variable is one node or relationship, and the WHERE there is checked for every repetition. Outside, the same variables are group variables: lists with one entry per repetition, in order (x, y and r above). The nodes before and after may be omitted. A repetition can span several relationships, and a named path (p = …) lists everything traversed.

A relationship is never used twice within one MATCH, which is also what stops an unbounded quantifier on a cyclic graph. A quantifier directly after a relationship is a shorter spelling of a variable-length relationship: -[:NEXT]->{1,3} is -[:NEXT*1..3]->.

Not supported: a quantified path pattern inside another, a variable-length relationship inside one, and shortestPath over one. A group variable cannot reuse the name of a variable bound outside the pattern. CREATE and MERGE need a fixed pattern.

Indexes and constraints · Procedure directory · Transactions and concurrency

Planning a deployment? Review compatibility and licence setup for your instance.