Overview

A shortest path between two nodes is the path that has the fewest edges. You can select shortest paths from the path pattern matching results with the following path search prefixes:

^[1] k: An non-negative integer. If fewer than k paths exist, all are retained.

When any of the above path searches is used, the path mode is compulsively set to TRAIL.

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

CREATE GRAPH myGraph { 
  NODE City ({name strig}),
  EDGE Links ()-[{}]->()
} PARTITION BY HASH(Crc32) SHARDS [1]

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 select all paths with the shortest length, use ALL SHORTEST.

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

Result: p

ANY SHORTEST

To select one shortest path in each partition, use ANY SHORTEST.

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

Result: p

SHORTEST k

To select k shortest paths in each partition, use SHORTEST k.

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

Result: p

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 select paths with the 1-st to k-th shortest lengths in each partition, use SHORTEST k GROUP. It 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 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:

MATCH p = SHORTEST 1 (a:City)-{,10}(b:City)
WHERE (a._id IN ['Zenith', 'Arcadia']) AND (b._id IN ['Eldoria', 'Nebula'])
RETURN p

Result: p

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: