Skip to main content

K_SHORTEST_PATHS

The K_SHORTEST_PATHS keyword in C8QL is used to find the top k shortest paths between two vertices in a graph. It computes a specified number of shortest paths (k) between a start vertex and a target vertex. This can be useful when you want to find alternative routes or paths in a network, such as finding several shortest routes in a transportation network or multiple connection chains in a social network.

For more information about using K_SHORTEST_PATHS, refer to K Shortest Path Queries.

Purpose

The purpose of the K_SHORTEST_PATH is to efficiently discover multiple shortest paths between two vertices in a graph. This allows users to analyze and compare alternative routes or paths based on various factors, such as cost, distance, or other attributes.

Syntax

Here's the general syntax for using the K_SHORTEST_PATHS keyword in C8QL:

FOR path IN
K_SHORTEST_PATHS start_vertex TO target_vertex
GRAPH 'graph_name'
OPTIONS { maxNumPaths: k, weightAttribute: 'attribute', defaultWeight: default_value }
RETURN path

Query Parameters

ParameterDescription
start_vertexThe starting vertex for the path search.
target_vertexThe target vertex that you want to find the k shortest paths to.
GRAPH 'graph_name'The name of the graph you want to search.
maxNumPaths: kThe number of shortest paths (k) you want to find.
OPTIONS options(Optional) Additional options to customize the path search.
- weightAttribute(string) The attribute to use as the weight for calculating the path length. By default, the algorithm uses the unweighted number of hops (edges) between vertices.
- defaultWeight(number) This value is used as fallback if there is no weightAttribute in the edge document, or if it's not a number. The default is 1.

Example

Here's an example of finding the three shortest paths between two users in a social network graph:

FOR path IN
K_SHORTEST_PATHS 'users/12345' TO 'users/67890'
GRAPH 'socialGraph'
OPTIONS { maxNumPaths: 3 }
RETURN path

This query finds the top three shortest paths between the user with the ID users/12345 and the user with the ID users/67890 in the socialGraph. The query returns an array of paths, each containing the vertices and edges in one of the three shortest paths.

If you need to find the k shortest paths based on a specific attribute, such as distance or cost, you can use the OPTIONS parameter to specify a weight attribute and a default weight value.

It's important to note that the K_SHORTEST_PATHS function might return fewer than k paths if there are fewer than k distinct paths between the given vertices. In such cases, it returns all the distinct paths that it can find.