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

This documentation is outdated. Please see the most recent stable version.

# 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
`vertices`

on the path. - An array containing the
`edges`

on 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 the`vertices`

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**startVertex**`TO`

**targetVertex**(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.`GRAPH`

**graphName**(string): the name identifying the named graph. Its vertex and edge collections will be looked up.

### 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:

```
var examples = require("@arangodb/graph-examples/example-graph");
var graph = examples.loadGraph("kShortestPathsGraph");
db.places.toArray();
db.connections.toArray();
```

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 }
```

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 }
```

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 }
```

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:

```
var examples = require("@arangodb/graph-examples/example-graph");
examples.dropGraph("kShortestPathsGraph");
```