Shortest paths

Find the cheapest route between two records, by the weight of its edges.

Syntax

Choose a verb, then the start, the end and the edge collection.

FOR p IN SHORTEST_PATH "gid://namespace/resource/a" TO "gid://namespace/resource/b" name_edge
FOR p IN K_SHORTEST_PATHS "…" TO "…" name_edge LIMIT 3

Parameters and arguments

  • verb

    SHORTEST_PATH: the route with the lowest total edge weight. ALL_SHORTEST_PATHS: every route that ties for cheapest. K_SHORTEST_PATHS: the k cheapest. K_PATHS: k distinct routes of any length

    Required: Yes
  • start and end

    Quoted GIDs, or variables that hold them, joined by TO

    Required: Yes
  • edge collection

    The name of the edge collection, or GRAPH "name"

    Required: Yes
  • LIMIT k

    How many routes the K verbs return. It is capped at 20

    Required: For the K verbs

Examples

Two records and an edge collection that has no edges, so there is no route.

Return type and behaviour

A route that exists is returned as found, from, to, totalWeight, depth, vertices and edges. The plural verbs return verb, k, from, to, pathCount and paths. A route is at most 10 edges long. When there is no route, the answer says found: false. For an edge collection that does not exist it also gives a reason, edge collection 'name' does not exist.

Errors and exceptions
ErrorWhat happenedHow to recover
HTQL-1003The traversal is not written in HTQL's grammarCheck the range, the direction, the start and the edge collection
HTQL-2012The edge collection's name is not in lower snake caseWrite a name such as placed_by_edge
PATH_SEARCH_TOO_LARGEThe edges reachable from the start within 10 hops number more than 250,000Use GRAPH "name" to keep only some labels
Limitations
  • Both ends are GIDs.
  • The most tied routes ALL_SHORTEST_PATHS returns is 100, and LIMIT above 20 is read as 20.
  • A search that reaches more than 250,000 edges is refused with PATH_SEARCH_TOO_LARGE. Narrow it with a named graph.
Best practices
  • Use SHORTEST_PATH for one route and the K verbs for alternatives.
  • Check found before you read a route.
  • Give edges a weight that means something, such as cost or distance, since that is what a route adds up.