Overview

A shortest path between two nodes is the path that has the fewest edges. The path pattern matching results can be restricted to the shortest paths by using the following shortest selectors:

^[1] k is an non-negative integer. If fewer than k shortest paths exist, all are retained. When k is missing, it defaults to 1.
^[2] The keywords GROUP and GROUPS can be used interchangeably as they do not affect the result.

Shortest paths are usually selected from the set of possible paths between two nodes in the graph, either with or without the constraint on length. Quantified path patterns allow you to specify a range of repetitions for certain segments of a path, facilitating the exploration of various possible paths.

To select the "cheapest" paths, which is analogous to the "shortest" but minimizes the sum of costs (edge weights) along a path, is not yet supported in GQL. If this functionality is required, you may consider using the UQL commands ab() or autonet() instead.

Subpath variables are not supported in shortest paths.

Example Graph

The following examples run against this graph:

To create this graph, run the following query against an empty graph:

INSERT (zenith:City {_id: "Zenith"}),
       (arcadia:City {_id: "Arcadia"}),
       (verona:City {_id: "Verona"}),
       (nebula:City {_id: "Nebula"}),
       (mirage:City {_id: "Mirage"}),
       (lunaria:City {_id: "Lunaria"}),
       (solara:City {_id: "Solara"}),
       (eldoria:City {_id: "Eldoria"}),
       (nexis:City {_id: "Nexis"}),
       (arcadia)-[:Links]->(zenith),
       (arcadia)-[:Links]->(verona),
       (arcadia)-[:Links]->(solara),
       (mirage)-[:Links]->(arcadia),
       (nebula)-[:Links]->(verona),
       (mirage)-[:Links]->(nebula),
       (verona)-[:Links]->(mirage),
       (mirage)-[:Links]->(eldoria),
       (solara)-[:Links]->(eldoria),
       (lunaria)-[:Links]->(solara)

ALL SHORTEST

To get all paths with the shortest length, use the selector ALL SHORTEST.

MATCH p = ALL SHORTEST (a)-{,10}(b)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p

Result:

SHORTEST k

To get k shortest paths in each partition, use the selector SHORTEST k.

MATCH p = SHORTEST 2 (a:City)-{,10}(b:City)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p

Result:

MATCH p = SHORTEST 3 (a:City)-{,10}(b:City)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p

Since only two paths with the shortest length of 2 exist between Arcadia and Eldoria, one path with the second shortest length needs to be selected. In this example, there is only one path with the second shortest length of 3, therefore the following three paths are returned:

SHORTEST k GROUP

To get paths with the 1-st to k-th shortest lengths in each partition, use the selector SHORTEST k GROUP. The selector groups paths by length and sorts the groups in ascending order by length, then selects all paths in the first k groups.

MATCH p = SHORTEST 3 GROUP (a:City)-[]-+(b:City)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p

Two paths with the shortest length of 2, one path with the second shortest length of 3 and one path with the third shortest length of 4 are returned:

Partitions

When a path pattern matches multiple start nodes and end nodes, the matching results are conceptually partitioned by the distinct pairs of start and end nodes. The selection of shortest paths is then performed within each partition.

In this query, the Cartesian product of a and b are generated before they are referenced in the shortest path pattern, therefore there are four shortest paths selected in total from the four partitions:

MMATCH p = SHORTEST 1 (a:City WHERE a._id = 'Zenith' OR a._id = 'Arcadia')-{,10}(b:City WHERE b._id = 'Eldoria' OR b._id = 'Nebula')
RETURN p

Result:

Single Source Shortest Paths

This query gets one shortest path between Arcadia and each other city:

MATCH p = SHORTEST 1 (c1:City {_id: 'Arcadia'})-{,10}(c2:City)
WHERE c2._id <> c1._id
RETURN p

There are 7 cities Arcadia can reach in the graph, while Nexis is not reachable. The following is one of the possible returns: