ArangoDB v3.9 reached End of Life (EOL) and is no longer supported.

This documentation is outdated. Please see the most recent version at docs.arangodb.com

Shortest Path in AQL

General query idea

This type of query is supposed to find the shortest path between two given documents (startVertex and targetVertex) in your graph. For all vertices on this shortest path you will get a result in form of a set with two items:

  1. The vertex on this path.
  2. The edge pointing to it.

Example execution

Let’s take a look at a simple example to explain how it works. This is the graph that we are going to find a shortest path on:

traversal graph

Now we use the following parameters for our query:

  1. We start at the vertex A.
  2. We finish with the vertex D.

So obviously we will have the vertices A, B, C and D on the shortest path in exactly this order. Than the shortest path statement will return the following pairs:

Vertex Edge
A null
B A → B
C B → C
D C → D

Note: The first edge will always be null because there is no edge pointing to the startVertex.

Syntax

Now let’s see how we can write a shortest path query. You have two options here, you can either use a named graph or a set of edge collections (anonymous graph).

Working with named graphs

FOR vertex[, edge]
  IN OUTBOUND|INBOUND|ANY SHORTEST_PATH
  startVertex TO targetVertex
  GRAPH graphName
  [OPTIONS options]
  • FOR: emits up to two variables:
    • vertex (object): the current vertex on the shortest path
    • edge (object, optional): the edge pointing to the vertex
  • IN OUTBOUND|INBOUND|ANY: defines in which direction edges are followed (outgoing, incoming, or both)
  • startVertex TO targetVertex (both string|object): the two vertices between which the shortest path will be computed. This can be specified in the form of an ID string or in the form of a document with the attribute _id. All other values will lead to 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.
  • GRAPH graphName (string): the name identifying the named graph. Its vertex and edge collections will be looked up.
  • OPTIONS options (object, optional): used to modify the execution of the traversal. Only the following attributes have an effect, all others are ignored:
    • weightAttribute (string): a top-level edge attribute that should be used to read the edge weight. If the attribute is not existent or not numeric, the defaultWeight will be used instead. The attribute value must not be negative.
    • defaultWeight (number): this value will be used as fallback if there is no weightAttribute in the edge document, or if it is not a number. The value must not be negative. The default is 1.

Shortest Path traversals do not support negative weights. If a document attribute (as specified by weightAttribute) with a negative value is encountered during traversal, or if defaultWeight is set to a negative number, then the query is aborted with an error.

Working with collection sets

FOR vertex[, edge]
  IN OUTBOUND|INBOUND|ANY SHORTEST_PATH
  startVertex TO targetVertex
  edgeCollection1, ..., edgeCollectionN
  [OPTIONS options]

Instead of GRAPH graphName you may specify a list of edge collections (anonymous graph). The involved vertex collections are determined by the edges of the given edge collections. The rest of the behavior is similar to the named version.

Traversing in mixed directions

For shortest path 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 general search direction and ANY specifically for edges2 as follows:

FOR vertex IN OUTBOUND SHORTEST_PATH
  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 to use a different direction for each collection in your path search.

Conditional shortest path

The SHORTEST_PATH computation will only find an unconditioned shortest path. With this construct it is not possible to define a condition like: “Find the shortest path where all edges are of type X”. If you want to do this, use a normal Traversal instead with the option {order: "bfs"} in combination with LIMIT 1.

Please also consider to use WITH to specify the collections you expect to be involved.

Examples

We will create a simple symmetric traversal demonstration graph:

traversal graph

arangosh> var examples = require("@arangodb/graph-examples/example-graph.js");
arangosh> var graph = examples.loadGraph("traversalGraph");
arangosh> db.circles.toArray();
arangosh> db.edges.toArray();
Show execution results
Hide execution results
[ 
  { 
    "_key" : "A", 
    "_id" : "circles/A", 
    "_rev" : "_gjDAjGG---", 
    "label" : "1" 
  }, 
  { 
    "_key" : "B", 
    "_id" : "circles/B", 
    "_rev" : "_gjDAjGG--_", 
    "label" : "2" 
  }, 
  { 
    "_key" : "C", 
    "_id" : "circles/C", 
    "_rev" : "_gjDAjGG--A", 
    "label" : "3" 
  }, 
  { 
    "_key" : "D", 
    "_id" : "circles/D", 
    "_rev" : "_gjDAjGG--B", 
    "label" : "4" 
  }, 
  { 
    "_key" : "E", 
    "_id" : "circles/E", 
    "_rev" : "_gjDAjGG--C", 
    "label" : "5" 
  }, 
  { 
    "_key" : "F", 
    "_id" : "circles/F", 
    "_rev" : "_gjDAjGG--D", 
    "label" : "6" 
  }, 
  { 
    "_key" : "G", 
    "_id" : "circles/G", 
    "_rev" : "_gjDAjGK---", 
    "label" : "7" 
  }, 
  { 
    "_key" : "H", 
    "_id" : "circles/H", 
    "_rev" : "_gjDAjGK--_", 
    "label" : "8" 
  }, 
  { 
    "_key" : "I", 
    "_id" : "circles/I", 
    "_rev" : "_gjDAjGK--A", 
    "label" : "9" 
  }, 
  { 
    "_key" : "J", 
    "_id" : "circles/J", 
    "_rev" : "_gjDAjGK--B", 
    "label" : "10" 
  }, 
  { 
    "_key" : "K", 
    "_id" : "circles/K", 
    "_rev" : "_gjDAjGK--C", 
    "label" : "11" 
  } 
]
[ 
  { 
    "_key" : "63121", 
    "_id" : "edges/63121", 
    "_from" : "circles/A", 
    "_to" : "circles/B", 
    "_rev" : "_gjDAjGK--D", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "left_bar" 
  }, 
  { 
    "_key" : "63123", 
    "_id" : "edges/63123", 
    "_from" : "circles/B", 
    "_to" : "circles/C", 
    "_rev" : "_gjDAjGK--E", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "left_blarg" 
  }, 
  { 
    "_key" : "63125", 
    "_id" : "edges/63125", 
    "_from" : "circles/C", 
    "_to" : "circles/D", 
    "_rev" : "_gjDAjGK--F", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "left_blorg" 
  }, 
  { 
    "_key" : "63127", 
    "_id" : "edges/63127", 
    "_from" : "circles/B", 
    "_to" : "circles/E", 
    "_rev" : "_gjDAjGK--G", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "left_blub" 
  }, 
  { 
    "_key" : "63129", 
    "_id" : "edges/63129", 
    "_from" : "circles/E", 
    "_to" : "circles/F", 
    "_rev" : "_gjDAjGK--H", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "left_schubi" 
  }, 
  { 
    "_key" : "63131", 
    "_id" : "edges/63131", 
    "_from" : "circles/A", 
    "_to" : "circles/G", 
    "_rev" : "_gjDAjGO---", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "right_foo" 
  }, 
  { 
    "_key" : "63133", 
    "_id" : "edges/63133", 
    "_from" : "circles/G", 
    "_to" : "circles/H", 
    "_rev" : "_gjDAjGO--_", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "right_blob" 
  }, 
  { 
    "_key" : "63135", 
    "_id" : "edges/63135", 
    "_from" : "circles/H", 
    "_to" : "circles/I", 
    "_rev" : "_gjDAjGO--A", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "right_blub" 
  }, 
  { 
    "_key" : "63137", 
    "_id" : "edges/63137", 
    "_from" : "circles/G", 
    "_to" : "circles/J", 
    "_rev" : "_gjDAjGO--B", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "right_zip" 
  }, 
  { 
    "_key" : "63139", 
    "_id" : "edges/63139", 
    "_from" : "circles/J", 
    "_to" : "circles/K", 
    "_rev" : "_gjDAjGO--C", 
    "theFalse" : false, 
    "theTruth" : true, 
    "label" : "right_zup" 
  } 
]

We start with the shortest path from A to D as above:

arangosh> db._query("FOR v, e IN OUTBOUND SHORTEST_PATH 'circles/A' TO 'circles/D' GRAPH 'traversalGraph' RETURN [v._key, e._key]");
arangosh> db._query("FOR v, e IN OUTBOUND SHORTEST_PATH 'circles/A' TO 'circles/D' edges RETURN [v._key, e._key]");
Show execution results
Hide execution results
[ 
  [ 
    "A", 
    null 
  ], 
  [ 
    "B", 
    "63121" 
  ], 
  [ 
    "C", 
    "63123" 
  ], 
  [ 
    "D", 
    "63125" 
  ] 
]
[object ArangoQueryCursor, count: 4, cached: false, hasMore: false]
[ 
  [ 
    "A", 
    null 
  ], 
  [ 
    "B", 
    "63121" 
  ], 
  [ 
    "C", 
    "63123" 
  ], 
  [ 
    "D", 
    "63125" 
  ] 
]
[object ArangoQueryCursor, count: 4, cached: false, hasMore: false]

We can see our expectations are fulfilled. We find the vertices in the correct ordering and the first edge is null, because no edge is pointing to the start vertex on t his path.

We can also compute shortest paths based on documents found in collections:

arangosh> db._query("FOR a IN circles FILTER a._key == 'A' FOR d IN circles FILTER d._key == 'D' FOR v, e IN OUTBOUND SHORTEST_PATH a TO d GRAPH 'traversalGraph' RETURN [v._key, e._key]");
arangosh> db._query("FOR a IN circles FILTER a._key == 'A' FOR d IN circles FILTER d._key == 'D' FOR v, e IN OUTBOUND SHORTEST_PATH a TO d edges RETURN [v._key, e._key]");
Show execution results
Hide execution results
[ 
  [ 
    "A", 
    null 
  ], 
  [ 
    "B", 
    "63121" 
  ], 
  [ 
    "C", 
    "63123" 
  ], 
  [ 
    "D", 
    "63125" 
  ] 
]
[object ArangoQueryCursor, count: 4, cached: false, hasMore: false]
[ 
  [ 
    "A", 
    null 
  ], 
  [ 
    "B", 
    "63121" 
  ], 
  [ 
    "C", 
    "63123" 
  ], 
  [ 
    "D", 
    "63125" 
  ] 
]
[object ArangoQueryCursor, count: 4, cached: false, hasMore: false]

And finally clean it up again:

arangosh> var examples = require("@arangodb/graph-examples/example-graph.js");
arangosh> examples.dropGraph("traversalGraph");
Show execution results
Hide execution results
(Empty output)
❮  Traversals

© ArangoDB - Graph and Beyond