Paths and shortest-path queries
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.
Related articles
Indexes and constraints · Procedure directory · Transactions and concurrency