# Paths and shortest-path queries

[Wiki](../README.md) / [Cypher query language](README.md)

**On this page**

- [Graph algorithms](#graph-algorithms)
  - [Procedures (weighted)](#procedures-weighted)
  - [shortestPath / allShortestPaths (unweighted, in MATCH)](#shortestpath--allshortestpaths-unweighted-in-match)
  - [Data-science similarity functions](#data-science-similarity-functions)

## 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](../gds/live-graph.md#graph-algorithms). For repeated
queries over a projected graph, use [projected pathfinding](../gds/pathfinding.md):
Dijkstra, A*, Yen and Hourglass.

```cypher
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`)

```cypher
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](../gds/similarity-functions.md#data-science-similarity-functions).

```cypher
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:

```cypher
// 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](../indexes/README.md) · [Procedure directory](../reference/procedures.md) · [Transactions and concurrency](../operations/transactions.md)
