All Shortest Paths in AQL
Find all paths of shortest length between a start and target vertex
General query idea
This type of query finds all paths of shortest length between two given documents (startVertex and targetVertex) in your graph.
Every returned path is a JSON object with two attributes:
- An array containing the
verticeson the path. - An array containing the
edgeson the path.
Example
A visual representation of the example graph:
Each ellipse stands for a train station with the name of the city written inside of it. They are the vertices of the graph. Arrows represent train connections between cities and are the edges of the graph.
Assuming that you want to go from Carlisle to London by train, the expected two shortest paths are:
- Carlisle – Birmingham – London
- Carlisle – York – London
Another path that connects Carlisle and London is Carlisle – Glasgow – Edinburgh – York – London, but it is has two more stops and is therefore not a path of the shortest length.
Syntax
The syntax for All Shortest Paths queries is similar to the one for
Shortest Path and there are also two options to
either use a named graph or a set of edge collections. It only emits a path
variable however, whereas SHORTEST_PATH emits a vertex and an edge variable.
Working with named graphs
FOR path
IN OUTBOUND|INBOUND|ANY ALL_SHORTEST_PATHS
startVertex TO targetVertex
GRAPH graphName
FOR: emits the variable path which contains one shortest path as an object, with theverticesandedgesof the path.INOUTBOUND|INBOUND|ANY: defines in which direction edges are followed (outgoing, incoming, or both)ALL_SHORTEST_PATHS: the keyword to compute All Shortest Paths- startVertex
TOtargetVertex (both string|object): the two vertices between which the paths will be computed. This can be specified in the form of a ID string or in the form of a document with the attribute_id. All other values result in a warning and an empty result. If one of the specified documents does not exist, the result is empty as well and there is no warning. GRAPHgraphName (string): the name identifying the named graph. Its vertex and edge collections will be looked up.
All Shortest Paths traversals do not support edge weights.
Working with collection sets
FOR path
IN OUTBOUND|INBOUND|ANY ALL_SHORTEST_PATHS
startVertex TO targetVertex
edgeCollection1, ..., edgeCollectionN
Instead of GRAPH graphName you can specify a list of edge collections.
The involved vertex collections are determined by the edges of the given
edge collections.
Traversing in mixed directions
For All Shortest Paths with a list of edge collections, you can optionally specify the
direction for some of the edge collections. Say, for example, you have three edge
collections edges1, edges2 and edges3, where in edges2 the direction
has no relevance, but in edges1 and edges3 the direction should be taken into
account. In this case you can use OUTBOUND as a general search direction and ANY
specifically for edges2 as follows:
FOR path IN OUTBOUND ALL_SHORTEST_PATHS
startVertex TO targetVertex
edges1, ANY edges2, edges3
All collections in the list that do not specify their own direction will use the
direction defined after IN (here: OUTBOUND). This allows using a different
direction for each collection in your path search.
Examples
Load an example graph to get a named graph that reflects some possible train connections in Europe and North America:
Suppose you want to query a route from Carlisle to London, and
compare the outputs of SHORTEST_PATH, K_SHORTEST_PATHS and ALL_SHORTEST_PATHS.
Note that SHORTEST_PATH returns any of the shortest paths, whereas
ALL_SHORTEST_PATHS returns all of them. K_SHORTEST_PATHS returns the
shortest paths first but continues with longer paths, until it found all routes
or reaches the defined limit (the number of paths).
Using SHORTEST_PATH to get one shortest path:
Using ALL_SHORTEST_PATHS to get both shortest paths:
Using K_SHORTEST_PATHS without a limit to get all paths in order of
increasing length:
If you ask for routes that don’t exist, you get an empty result (from Carlisle to Toronto):
FOR p IN OUTBOUND ALL_SHORTEST_PATHS 'places/Carlisle' TO 'places/Toronto'
GRAPH 'kShortestPathsGraph'
RETURN {
places: p.vertices[*].label
}
[]
And finally clean up by removing the named graph:
arangosh> var examples = require("@arangodb/graph-examples/example-graph.js");
arangosh> examples.dropGraph("kShortestPathsGraph");