ArangoDB Logo

All Shortest Paths in AQL

Find all paths of shortest length between two nodes

General query idea

This type of query finds all paths of shortest length between two given documents (startNode and endNode) in your graph.

Every returned path is a JSON object with two attributes:

  • An array containing the vertices on the path.
  • An array containing the edges on the path.

Example

A visual representation of the example graph:

Train Connection Map

Each ellipse stands for a train station with the name of the city written inside of it. They are the nodes 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:

  1. Carlisle – Birmingham – London
  2. Carlisle – York – London

Another path that connects Carlisle and London is Carlisle – Glasgow – Edinburgh – York – London, but it 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 node and an edge variable.

Working with named graphs 

FOR path
  IN OUTBOUND|INBOUND|ANY ALL_SHORTEST_PATHS
  startNode TO endNode
  GRAPH graphName
  [OPTIONS options]
  • FOR: Emits the variable path which contains one shortest path as an object, with the vertices (nodes) and edges of the path.
  • IN OUTBOUND|INBOUND|ANY: Defines in which direction edges are followed (outgoing, incoming, or both)
  • ALL_SHORTEST_PATHS: The keyword to compute All Shortest Paths
  • startNode TO endNode (both string|object): The two nodes between which the paths are 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.
  • GRAPH graphName (string): The name identifying the named graph. Its node and edge collections are looked up for the path search.
  • OPTIONS options (object, optional): See the path search options.
All Shortest Paths traversals do not support edge weights.

Working with collection sets 

FOR path
  IN OUTBOUND|INBOUND|ANY ALL_SHORTEST_PATHS
  startNode TO endNode
  edgeCollection1, ..., edgeCollectionN

Instead of GRAPH graphName you can specify a list of edge collections. The involved node collections are determined by the edges of the given edge collections.

Path search options

You can optionally specify the following options to modify the execution of a graph path search. If you specify unknown options, query warnings are raised.

useCache

Introduced in: v3.12.2

Whether to use the in-memory cache for edges. The default is true.

You can set this option to false to not make a large graph operation pollute the edge cache.

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
  startNode TO endNode
  edges1, ANY edges2, edges3

All collections in the list that do not specify their own direction use the direction defined after IN (here: OUTBOUND). This allows using a different direction for each collection in your path search.

Graph path searches in a cluster

Due to the nature of graphs, edges may reference nodes from arbitrary collections. Following the paths can thus involve documents from various collections and it is not possible to predict which are visited in a traversal. Which collections need to be loaded by the graph engine can only be determined at run time.

Use the WITH operation to specify the node collections you expect to be involved. This is required for traversals using collection sets in cluster deployments. Declare the collection of the start node as well if it’s not declared already (like by a FOR loop).

From v3.12.6 onward, node collections are automatically deduced for graph queries using collection sets / anonymous graphs if there is a named graph with a matching edge collection in its edge definitions.

For example, suppose you have two node collections, person and movie, and an acts_in edge collection that connects them. If you want to run a path search query that starts (and ends) at a person that you specify with its document ID, you need to declare both node collections at the beginning of the query:

WITH person, movie
FOR p IN ANY ALL_SHORTEST_PATHS "person/1544" TO "person/52560" acts_in
  RETURN p.vertices[*].label

However, if there is a named graph that includes an edge definition for the acts_in edge collection, with person as the from collection and movie as the to collection, you can omit WITH person, movie. That is, if you specify acts_in as an edge collection in an anonymous graph query, all named graphs are checked for this edge collection, and if there is a matching edge definition, its node collections are automatically added as data sources to the query.

FOR p IN ANY ALL_SHORTEST_PATHS "person/1544" TO "person/52560" acts_in
  RETURN p.vertices[*].label

// Chris Rock --> Dogma <-- Ben Affleck --> Surviving Christmas <-- Jennifer Morrison
// Chris Rock --> The Longest Yard <-- Rob Schneider --> Big Stan <-- Jennifer Morrison
// Chris Rock --> Down to Earth <-- John Cho --> Star Trek <-- Jennifer Morrison

You can still declare collections manually, in which case they are added as data sources in addition to automatically deduced collections.

Examples

Load an example graph to get a named graph that reflects some possible train connections in Europe and North America:

Train Connection Map

var examples = require("@arangodb/graph-examples/example-graph");
var graph = examples.loadGraph("kShortestPathsGraph");
db.places.toArray();
db.connections.toArray();
Show output
[ 
  { 
    "_key" : "Inverness", 
    "_id" : "places/Inverness", 
    "_rev" : "_kgUtVEC---", 
    "label" : "Inverness" 
  }, 
  { 
    "_key" : "Aberdeen", 
    "_id" : "places/Aberdeen", 
    "_rev" : "_kgUtVEC--_", 
    "label" : "Aberdeen" 
  }, 
  { 
    "_key" : "Leuchars", 
    "_id" : "places/Leuchars", 
    "_rev" : "_kgUtVEG---", 
    "label" : "Leuchars" 
  }, 
  { 
    "_key" : "StAndrews", 
    "_id" : "places/StAndrews", 
    "_rev" : "_kgUtVEG--_", 
    "label" : "StAndrews" 
  }, 
  { 
    "_key" : "Edinburgh", 
    "_id" : "places/Edinburgh", 
    "_rev" : "_kgUtVEG--A", 
    "label" : "Edinburgh" 
  }, 
  { 
    "_key" : "Glasgow", 
    "_id" : "places/Glasgow", 
    "_rev" : "_kgUtVEG--B", 
    "label" : "Glasgow" 
  }, 
  { 
    "_key" : "York", 
    "_id" : "places/York", 
    "_rev" : "_kgUtVEK---", 
    "label" : "York" 
  }, 
  { 
    "_key" : "Carlisle", 
    "_id" : "places/Carlisle", 
    "_rev" : "_kgUtVEK--_", 
    "label" : "Carlisle" 
  }, 
  { 
    "_key" : "Birmingham", 
    "_id" : "places/Birmingham", 
    "_rev" : "_kgUtVEK--A", 
    "label" : "Birmingham" 
  }, 
  { 
    "_key" : "London", 
    "_id" : "places/London", 
    "_rev" : "_kgUtVEK--B", 
    "label" : "London" 
  }, 
  { 
    "_key" : "Brussels", 
    "_id" : "places/Brussels", 
    "_rev" : "_kgUtVEK--C", 
    "label" : "Brussels" 
  }, 
  { 
    "_key" : "Cologne", 
    "_id" : "places/Cologne", 
    "_rev" : "_kgUtVEK--D", 
    "label" : "Cologne" 
  }, 
  { 
    "_key" : "Toronto", 
    "_id" : "places/Toronto", 
    "_rev" : "_kgUtVEO---", 
    "label" : "Toronto" 
  }, 
  { 
    "_key" : "Winnipeg", 
    "_id" : "places/Winnipeg", 
    "_rev" : "_kgUtVEO--_", 
    "label" : "Winnipeg" 
  }, 
  { 
    "_key" : "Saskatoon", 
    "_id" : "places/Saskatoon", 
    "_rev" : "_kgUtVEO--A", 
    "label" : "Saskatoon" 
  }, 
  { 
    "_key" : "Edmonton", 
    "_id" : "places/Edmonton", 
    "_rev" : "_kgUtVEO--B", 
    "label" : "Edmonton" 
  }, 
  { 
    "_key" : "Jasper", 
    "_id" : "places/Jasper", 
    "_rev" : "_kgUtVEO--C", 
    "label" : "Jasper" 
  }, 
  { 
    "_key" : "Vancouver", 
    "_id" : "places/Vancouver", 
    "_rev" : "_kgUtVES---", 
    "label" : "Vancouver" 
  } 
]

[ 
  { 
    "_key" : "63496", 
    "_id" : "connections/63496", 
    "_from" : "places/Inverness", 
    "_to" : "places/Aberdeen", 
    "_rev" : "_kgUtVES--_", 
    "travelTime" : 3 
  }, 
  { 
    "_key" : "63498", 
    "_id" : "connections/63498", 
    "_from" : "places/Aberdeen", 
    "_to" : "places/Inverness", 
    "_rev" : "_kgUtVES--A", 
    "travelTime" : 2.5 
  }, 
  { 
    "_key" : "63500", 
    "_id" : "connections/63500", 
    "_from" : "places/Aberdeen", 
    "_to" : "places/Leuchars", 
    "_rev" : "_kgUtVES--B", 
    "travelTime" : 1.5 
  }, 
  { 
    "_key" : "63502", 
    "_id" : "connections/63502", 
    "_from" : "places/Leuchars", 
    "_to" : "places/Aberdeen", 
    "_rev" : "_kgUtVES--C", 
    "travelTime" : 1 
  }, 
  { 
    "_key" : "63504", 
    "_id" : "connections/63504", 
    "_from" : "places/Leuchars", 
    "_to" : "places/Edinburgh", 
    "_rev" : "_kgUtVEW---", 
    "travelTime" : 1.5 
  }, 
  { 
    "_key" : "63506", 
    "_id" : "connections/63506", 
    "_from" : "places/Edinburgh", 
    "_to" : "places/Leuchars", 
    "_rev" : "_kgUtVEW--_", 
    "travelTime" : 3 
  }, 
  { 
    "_key" : "63508", 
    "_id" : "connections/63508", 
    "_from" : "places/Edinburgh", 
    "_to" : "places/Glasgow", 
    "_rev" : "_kgUtVEW--A", 
    "travelTime" : 1 
  }, 
  { 
    "_key" : "63510", 
    "_id" : "connections/63510", 
    "_from" : "places/Glasgow", 
    "_to" : "places/Edinburgh", 
    "_rev" : "_kgUtVEW--B", 
    "travelTime" : 1 
  }, 
  { 
    "_key" : "63512", 
    "_id" : "connections/63512", 
    "_from" : "places/Edinburgh", 
    "_to" : "places/York", 
    "_rev" : "_kgUtVEW--C", 
    "travelTime" : 3.5 
  }, 
  { 
    "_key" : "63514", 
    "_id" : "connections/63514", 
    "_from" : "places/York", 
    "_to" : "places/Edinburgh", 
    "_rev" : "_kgUtVEa---", 
    "travelTime" : 4 
  }, 
  { 
    "_key" : "63516", 
    "_id" : "connections/63516", 
    "_from" : "places/Glasgow", 
    "_to" : "places/Carlisle", 
    "_rev" : "_kgUtVEa--_", 
    "travelTime" : 1 
  }, 
  { 
    "_key" : "63518", 
    "_id" : "connections/63518", 
    "_from" : "places/Carlisle", 
    "_to" : "places/Glasgow", 
    "_rev" : "_kgUtVEa--A", 
    "travelTime" : 1 
  }, 
  { 
    "_key" : "63520", 
    "_id" : "connections/63520", 
    "_from" : "places/Carlisle", 
    "_to" : "places/York", 
    "_rev" : "_kgUtVEa--B", 
    "travelTime" : 2.5 
  }, 
  { 
    "_key" : "63522", 
    "_id" : "connections/63522", 
    "_from" : "places/York", 
    "_to" : "places/Carlisle", 
    "_rev" : "_kgUtVEa--C", 
    "travelTime" : 3.5 
  }, 
  { 
    "_key" : "63524", 
    "_id" : "connections/63524", 
    "_from" : "places/Carlisle", 
    "_to" : "places/Birmingham", 
    "_rev" : "_kgUtVEe---", 
    "travelTime" : 2 
  }, 
  { 
    "_key" : "63526", 
    "_id" : "connections/63526", 
    "_from" : "places/Birmingham", 
    "_to" : "places/Carlisle", 
    "_rev" : "_kgUtVEe--_", 
    "travelTime" : 1 
  }, 
  { 
    "_key" : "63528", 
    "_id" : "connections/63528", 
    "_from" : "places/Birmingham", 
    "_to" : "places/London", 
    "_rev" : "_kgUtVEe--A", 
    "travelTime" : 1.5 
  }, 
  { 
    "_key" : "63530", 
    "_id" : "connections/63530", 
    "_from" : "places/London", 
    "_to" : "places/Birmingham", 
    "_rev" : "_kgUtVEe--B", 
    "travelTime" : 2.5 
  }, 
  { 
    "_key" : "63532", 
    "_id" : "connections/63532", 
    "_from" : "places/Leuchars", 
    "_to" : "places/StAndrews", 
    "_rev" : "_kgUtVEe--C", 
    "travelTime" : 0.2 
  }, 
  { 
    "_key" : "63534", 
    "_id" : "connections/63534", 
    "_from" : "places/StAndrews", 
    "_to" : "places/Leuchars", 
    "_rev" : "_kgUtVEi---", 
    "travelTime" : 0.2 
  }, 
  { 
    "_key" : "63536", 
    "_id" : "connections/63536", 
    "_from" : "places/York", 
    "_to" : "places/London", 
    "_rev" : "_kgUtVEi--_", 
    "travelTime" : 1.8 
  }, 
  { 
    "_key" : "63538", 
    "_id" : "connections/63538", 
    "_from" : "places/London", 
    "_to" : "places/York", 
    "_rev" : "_kgUtVEi--A", 
    "travelTime" : 2 
  }, 
  { 
    "_key" : "63540", 
    "_id" : "connections/63540", 
    "_from" : "places/London", 
    "_to" : "places/Brussels", 
    "_rev" : "_kgUtVEi--B", 
    "travelTime" : 2.5 
  }, 
  { 
    "_key" : "63542", 
    "_id" : "connections/63542", 
    "_from" : "places/Brussels", 
    "_to" : "places/London", 
    "_rev" : "_kgUtVEi--C", 
    "travelTime" : 3.5 
  }, 
  { 
    "_key" : "63544", 
    "_id" : "connections/63544", 
    "_from" : "places/Brussels", 
    "_to" : "places/Cologne", 
    "_rev" : "_kgUtVEm---", 
    "travelTime" : 2 
  }, 
  { 
    "_key" : "63546", 
    "_id" : "connections/63546", 
    "_from" : "places/Cologne", 
    "_to" : "places/Brussels", 
    "_rev" : "_kgUtVEm--_", 
    "travelTime" : 1.5 
  }, 
  { 
    "_key" : "63548", 
    "_id" : "connections/63548", 
    "_from" : "places/Toronto", 
    "_to" : "places/Winnipeg", 
    "_rev" : "_kgUtVEm--A", 
    "travelTime" : 36 
  }, 
  { 
    "_key" : "63550", 
    "_id" : "connections/63550", 
    "_from" : "places/Winnipeg", 
    "_to" : "places/Toronto", 
    "_rev" : "_kgUtVEm--B", 
    "travelTime" : 35 
  }, 
  { 
    "_key" : "63552", 
    "_id" : "connections/63552", 
    "_from" : "places/Winnipeg", 
    "_to" : "places/Saskatoon", 
    "_rev" : "_kgUtVEm--C", 
    "travelTime" : 12 
  }, 
  { 
    "_key" : "63554", 
    "_id" : "connections/63554", 
    "_from" : "places/Saskatoon", 
    "_to" : "places/Winnipeg", 
    "_rev" : "_kgUtVEq---", 
    "travelTime" : 5 
  }, 
  { 
    "_key" : "63556", 
    "_id" : "connections/63556", 
    "_from" : "places/Saskatoon", 
    "_to" : "places/Edmonton", 
    "_rev" : "_kgUtVEq--_", 
    "travelTime" : 12 
  }, 
  { 
    "_key" : "63558", 
    "_id" : "connections/63558", 
    "_from" : "places/Edmonton", 
    "_to" : "places/Saskatoon", 
    "_rev" : "_kgUtVEq--A", 
    "travelTime" : 17 
  }, 
  { 
    "_key" : "63560", 
    "_id" : "connections/63560", 
    "_from" : "places/Edmonton", 
    "_to" : "places/Jasper", 
    "_rev" : "_kgUtVEq--B", 
    "travelTime" : 6 
  }, 
  { 
    "_key" : "63562", 
    "_id" : "connections/63562", 
    "_from" : "places/Jasper", 
    "_to" : "places/Edmonton", 
    "_rev" : "_kgUtVEu---", 
    "travelTime" : 5 
  }, 
  { 
    "_key" : "63564", 
    "_id" : "connections/63564", 
    "_from" : "places/Jasper", 
    "_to" : "places/Vancouver", 
    "_rev" : "_kgUtVEu--_", 
    "travelTime" : 12 
  }, 
  { 
    "_key" : "63566", 
    "_id" : "connections/63566", 
    "_from" : "places/Vancouver", 
    "_to" : "places/Jasper", 
    "_rev" : "_kgUtVEu--A", 
    "travelTime" : 13 
  } 
]

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:

FOR v, e IN OUTBOUND SHORTEST_PATH 'places/Carlisle' TO 'places/London'
GRAPH 'kShortestPathsGraph'
  RETURN { place: v.label }
Show output
[ 
  { 
    "place" : "Carlisle" 
  }, 
  { 
    "place" : "York" 
  }, 
  { 
    "place" : "London" 
  } 
]

Using ALL_SHORTEST_PATHS to get both shortest paths:

FOR p IN OUTBOUND ALL_SHORTEST_PATHS 'places/Carlisle' TO 'places/London'
GRAPH 'kShortestPathsGraph'
  RETURN { places: p.vertices[*].label }
Show output
[ 
  { 
    "places" : [ 
      "Carlisle", 
      "York", 
      "London" 
    ] 
  }, 
  { 
    "places" : [ 
      "Carlisle", 
      "Birmingham", 
      "London" 
    ] 
  } 
]

Using K_SHORTEST_PATHS without a limit to get all paths in order of increasing length:

FOR p IN OUTBOUND K_SHORTEST_PATHS 'places/Carlisle' TO 'places/London'
GRAPH 'kShortestPathsGraph'
  RETURN { places: p.vertices[*].label }
Show output
[ 
  { 
    "places" : [ 
      "Carlisle", 
      "York", 
      "London" 
    ] 
  }, 
  { 
    "places" : [ 
      "Carlisle", 
      "Birmingham", 
      "London" 
    ] 
  }, 
  { 
    "places" : [ 
      "Carlisle", 
      "Glasgow", 
      "Edinburgh", 
      "York", 
      "London" 
    ] 
  } 
]

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
  }
Show output
[ ]

And finally clean up by removing the named graph:

var examples = require("@arangodb/graph-examples/example-graph");
examples.dropGraph("kShortestPathsGraph");
Show output
Empty Output

On this page