# k Shortest Paths in AQL

## General query idea

This type of query finds the first k paths in order of length (or weight) between two given documents, startVertex and targetVertex in your graph.

Every such path will be returned as a JSON object with three components:

• an array containing the `vertices` on the path
• an array containing the `edges` on the path
• the `weight` of the path, that is the sum of all edge weights

If no `weightAttribute` is given, the weight of the path is just its length.

Example

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

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. The numbers near the arrows describe how long it takes to get from one station to another. They are used as edge weights.

Let us assume that we want to go from Aberdeen to London by train.

We expect to see the following vertices on the shortest path, in this order:

1. Aberdeen
2. Leuchars
3. Edinburgh
4. York
5. London

By the way, the weight of the path is: 1.5 + 1.5 + 3.5 + 1.8 = 8.3.

Let us look at alternative paths next, for example because we know that the direct connection between York and London does not operate currently. An alternative path, which is slightly longer, goes like this:

1. Aberdeen
2. Leuchars
3. Edinburgh
4. York
5. Carlisle
6. Birmingham
7. London

Its weight is: 1.5 + 1.5 + 3.5 + 2.0 + 1.5 = 10.0.

Another route goes via Glasgow. There are seven stations on the path as well, however, it is quicker if we compare the edge weights:

1. Aberdeen
2. Leuchars
3. Edinburgh
4. Glasgow
5. Carlisle
6. Birmingham
7. London

The path weight is lower: 1.5 + 1.5 + 1.0 + 1.0 + 2.0 + 1.5 = 8.5.

## Syntax

The syntax for k 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.

It is highly recommended that you use a LIMIT statement, as k Shortest Paths is a potentially expensive operation. On large connected graphs it can return a large number of paths, or perform an expensive (but unsuccessful) search for more short paths.

### Working with named graphs

``````FOR path
IN OUTBOUND|INBOUND|ANY K_SHORTEST_PATHS
startVertex TO targetVertex
GRAPH graphName
[OPTIONS options]
[LIMIT offset, count]
``````
• `FOR`: emits the variable path which contains one path as an object containing `vertices`, `edges`, and the `weight` of the path.
• `IN` `OUTBOUND|INBOUND|ANY`: defines in which direction edges are followed (outgoing, incoming, or both)
• `K_SHORTEST_PATHS`: the keyword to compute k 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 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 does not exist or is 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’s not a number. The value must not be negative. The default is `1`.
• `LIMIT` (see LIMIT operation, optional): the maximal number of paths to return. It is highly recommended to use a `LIMIT` for `K_SHORTEST_PATHS`.

k Shortest Paths 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 path
IN OUTBOUND|INBOUND|ANY K_SHORTEST_PATHS
startVertex TO targetVertex
edgeCollection1, ..., edgeCollectionN
[OPTIONS options]
[LIMIT offset, count]
``````

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 k 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 general search direction and `ANY` specifically for edges2 as follows:

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

## Examples

We load an example graph to get a named graph that reflects some possible train connections in Europe and North America.

```arangosh> var examples = require("@arangodb/graph-examples/example-graph.js");
arangosh> var graph = examples.loadGraph("kShortestPathsGraph");
arangosh> db.places.toArray();
arangosh> db.connections.toArray();```
```[
{
"_key" : "Inverness",
"_id" : "places/Inverness",
"_rev" : "_eFDzr1W---",
"label" : "Inverness"
},
{
"_key" : "Aberdeen",
"_id" : "places/Aberdeen",
"_rev" : "_eFDzr1a---",
"label" : "Aberdeen"
},
{
"_key" : "Leuchars",
"_id" : "places/Leuchars",
"_rev" : "_eFDzr1a--_",
"label" : "Leuchars"
},
{
"_key" : "StAndrews",
"_id" : "places/StAndrews",
"_rev" : "_eFDzr1e---",
"label" : "StAndrews"
},
{
"_key" : "Edinburgh",
"_id" : "places/Edinburgh",
"_rev" : "_eFDzr1e--_",
"label" : "Edinburgh"
},
{
"_key" : "Glasgow",
"_id" : "places/Glasgow",
"_rev" : "_eFDzr1i---",
"label" : "Glasgow"
},
{
"_key" : "York",
"_id" : "places/York",
"_rev" : "_eFDzr1i--_",
"label" : "York"
},
{
"_key" : "Carlisle",
"_id" : "places/Carlisle",
"_rev" : "_eFDzr1i--A",
"label" : "Carlisle"
},
{
"_key" : "Birmingham",
"_id" : "places/Birmingham",
"_rev" : "_eFDzr1m---",
"label" : "Birmingham"
},
{
"_key" : "London",
"_id" : "places/London",
"_rev" : "_eFDzr1m--_",
"label" : "London"
},
{
"_key" : "Brussels",
"_id" : "places/Brussels",
"_rev" : "_eFDzr1m--A",
"label" : "Brussels"
},
{
"_key" : "Cologne",
"_id" : "places/Cologne",
"_rev" : "_eFDzr1q---",
"label" : "Cologne"
},
{
"_key" : "Toronto",
"_id" : "places/Toronto",
"_rev" : "_eFDzr1q--_",
"label" : "Toronto"
},
{
"_key" : "Winnipeg",
"_id" : "places/Winnipeg",
"_rev" : "_eFDzr1q--A",
"label" : "Winnipeg"
},
{
"_key" : "Saskatoon",
"_id" : "places/Saskatoon",
"_rev" : "_eFDzr1u---",
"label" : "Saskatoon"
},
{
"_key" : "Edmonton",
"_id" : "places/Edmonton",
"_rev" : "_eFDzr1u--_",
"label" : "Edmonton"
},
{
"_key" : "Jasper",
"_id" : "places/Jasper",
"_rev" : "_eFDzr1u--A",
"label" : "Jasper"
},
{
"_key" : "Vancouver",
"_id" : "places/Vancouver",
"_rev" : "_eFDzr1y---",
"label" : "Vancouver"
}
]
[
{
"_key" : "62481",
"_id" : "connections/62481",
"_from" : "places/Inverness",
"_to" : "places/Aberdeen",
"_rev" : "_eFDzr1y--_",
"travelTime" : 3
},
{
"_key" : "62483",
"_id" : "connections/62483",
"_from" : "places/Aberdeen",
"_to" : "places/Inverness",
"_rev" : "_eFDzr12---",
"travelTime" : 2.5
},
{
"_key" : "62485",
"_id" : "connections/62485",
"_from" : "places/Aberdeen",
"_to" : "places/Leuchars",
"_rev" : "_eFDzr12--_",
"travelTime" : 1.5
},
{
"_key" : "62487",
"_id" : "connections/62487",
"_from" : "places/Leuchars",
"_to" : "places/Aberdeen",
"_rev" : "_eFDzr12--A",
"travelTime" : 1
},
{
"_key" : "62489",
"_id" : "connections/62489",
"_from" : "places/Leuchars",
"_to" : "places/Edinburgh",
"_rev" : "_eFDzr16---",
"travelTime" : 1.5
},
{
"_key" : "62491",
"_id" : "connections/62491",
"_from" : "places/Edinburgh",
"_to" : "places/Leuchars",
"_rev" : "_eFDzr16--_",
"travelTime" : 3
},
{
"_key" : "62493",
"_id" : "connections/62493",
"_from" : "places/Edinburgh",
"_to" : "places/Glasgow",
"_rev" : "_eFDzr16--A",
"travelTime" : 1
},
{
"_key" : "62495",
"_id" : "connections/62495",
"_from" : "places/Glasgow",
"_to" : "places/Edinburgh",
"_rev" : "_eFDzr2----",
"travelTime" : 1
},
{
"_key" : "62497",
"_id" : "connections/62497",
"_from" : "places/Edinburgh",
"_to" : "places/York",
"_rev" : "_eFDzr2---_",
"travelTime" : 3.5
},
{
"_key" : "62499",
"_id" : "connections/62499",
"_from" : "places/York",
"_to" : "places/Edinburgh",
"_rev" : "_eFDzr2C---",
"travelTime" : 4
},
{
"_key" : "62501",
"_id" : "connections/62501",
"_from" : "places/Glasgow",
"_to" : "places/Carlisle",
"_rev" : "_eFDzr2C--_",
"travelTime" : 1
},
{
"_key" : "62503",
"_id" : "connections/62503",
"_from" : "places/Carlisle",
"_to" : "places/Glasgow",
"_rev" : "_eFDzr2C--A",
"travelTime" : 1
},
{
"_key" : "62505",
"_id" : "connections/62505",
"_from" : "places/Carlisle",
"_to" : "places/York",
"_rev" : "_eFDzr2G---",
"travelTime" : 2.5
},
{
"_key" : "62507",
"_id" : "connections/62507",
"_from" : "places/York",
"_to" : "places/Carlisle",
"_rev" : "_eFDzr2G--_",
"travelTime" : 3.5
},
{
"_key" : "62509",
"_id" : "connections/62509",
"_from" : "places/Carlisle",
"_to" : "places/Birmingham",
"_rev" : "_eFDzr2K---",
"travelTime" : 2
},
{
"_key" : "62511",
"_id" : "connections/62511",
"_from" : "places/Birmingham",
"_to" : "places/Carlisle",
"_rev" : "_eFDzr2K--_",
"travelTime" : 1
},
{
"_key" : "62513",
"_id" : "connections/62513",
"_from" : "places/Birmingham",
"_to" : "places/London",
"_rev" : "_eFDzr2K--A",
"travelTime" : 1.5
},
{
"_key" : "62515",
"_id" : "connections/62515",
"_from" : "places/London",
"_to" : "places/Birmingham",
"_rev" : "_eFDzr2O---",
"travelTime" : 2.5
},
{
"_key" : "62517",
"_id" : "connections/62517",
"_from" : "places/Leuchars",
"_to" : "places/StAndrews",
"_rev" : "_eFDzr2O--_",
"travelTime" : 0.2
},
{
"_key" : "62519",
"_id" : "connections/62519",
"_from" : "places/StAndrews",
"_to" : "places/Leuchars",
"_rev" : "_eFDzr2O--A",
"travelTime" : 0.2
},
{
"_key" : "62521",
"_id" : "connections/62521",
"_from" : "places/York",
"_to" : "places/London",
"_rev" : "_eFDzr2S---",
"travelTime" : 1.8
},
{
"_key" : "62523",
"_id" : "connections/62523",
"_from" : "places/London",
"_to" : "places/York",
"_rev" : "_eFDzr2S--_",
"travelTime" : 2
},
{
"_key" : "62525",
"_id" : "connections/62525",
"_from" : "places/London",
"_to" : "places/Brussels",
"_rev" : "_eFDzr2W---",
"travelTime" : 2.5
},
{
"_key" : "62527",
"_id" : "connections/62527",
"_from" : "places/Brussels",
"_to" : "places/London",
"_rev" : "_eFDzr2W--_",
"travelTime" : 3.5
},
{
"_key" : "62529",
"_id" : "connections/62529",
"_from" : "places/Brussels",
"_to" : "places/Cologne",
"_rev" : "_eFDzr2a---",
"travelTime" : 2
},
{
"_key" : "62531",
"_id" : "connections/62531",
"_from" : "places/Cologne",
"_to" : "places/Brussels",
"_rev" : "_eFDzr2a--_",
"travelTime" : 1.5
},
{
"_key" : "62533",
"_id" : "connections/62533",
"_from" : "places/Toronto",
"_to" : "places/Winnipeg",
"_rev" : "_eFDzr2a--A",
"travelTime" : 36
},
{
"_key" : "62535",
"_id" : "connections/62535",
"_from" : "places/Winnipeg",
"_to" : "places/Toronto",
"_rev" : "_eFDzr2e---",
"travelTime" : 35
},
{
"_key" : "62537",
"_id" : "connections/62537",
"_from" : "places/Winnipeg",
"_to" : "places/Saskatoon",
"_rev" : "_eFDzr2e--_",
"travelTime" : 12
},
{
"_key" : "62539",
"_id" : "connections/62539",
"_from" : "places/Saskatoon",
"_to" : "places/Winnipeg",
"_rev" : "_eFDzr2i---",
"travelTime" : 5
},
{
"_key" : "62541",
"_id" : "connections/62541",
"_from" : "places/Saskatoon",
"_to" : "places/Edmonton",
"_rev" : "_eFDzr2i--_",
"travelTime" : 12
},
{
"_key" : "62543",
"_id" : "connections/62543",
"_from" : "places/Edmonton",
"_to" : "places/Saskatoon",
"_rev" : "_eFDzr2i--A",
"travelTime" : 17
},
{
"_key" : "62545",
"_id" : "connections/62545",
"_from" : "places/Edmonton",
"_to" : "places/Jasper",
"_rev" : "_eFDzr2m---",
"travelTime" : 6
},
{
"_key" : "62547",
"_id" : "connections/62547",
"_from" : "places/Jasper",
"_to" : "places/Edmonton",
"_rev" : "_eFDzr2m--_",
"travelTime" : 5
},
{
"_key" : "62549",
"_id" : "connections/62549",
"_from" : "places/Jasper",
"_to" : "places/Vancouver",
"_rev" : "_eFDzr2m--A",
"travelTime" : 12
},
{
"_key" : "62551",
"_id" : "connections/62551",
"_from" : "places/Vancouver",
"_to" : "places/Jasper",
"_rev" : "_eFDzr2q---",
"travelTime" : 13
}
]```

Suppose we want to query a route from Aberdeen to London, and compare the outputs of `SHORTEST_PATH` and `K_SHORTEST_PATHS` with `LIMIT 1`. Note that while `SHORTEST_PATH` and `K_SHORTEST_PATH` with `LIMIT 1` should return a path of the same length (or weight), they do not need to return the same path.

Using `SHORTEST_PATH`:

```FOR v, e IN OUTBOUND SHORTEST_PATH 'places/Aberdeen' TO 'places/London'
GRAPH 'kShortestPathsGraph'
RETURN { place: v.label, travelTime: e.travelTime }```
```[
{
"place": "Aberdeen",
"travelTime": null
},
{
"place": "Leuchars",
"travelTime": 1.5
},
{
"place": "Edinburgh",
"travelTime": 1.5
},
{
"place": "York",
"travelTime": 3.5
},
{
"place": "London",
"travelTime": 1.8
}
]```

Using `K_SHORTEST_PATHS`:

```FOR p IN OUTBOUND K_SHORTEST_PATHS 'places/Aberdeen' TO 'places/London'
GRAPH 'kShortestPathsGraph'
LIMIT 1
RETURN { places: p.vertices[*].label, travelTimes: p.edges[*].travelTime }```
```[
{
"places": [
"Aberdeen",
"Leuchars",
"Edinburgh",
"York",
"London"
],
"travelTimes": [
1.5,
1.5,
3.5,
1.8
]
}
]```

With `K_SHORTEST_PATHS` we can ask for more than one option for a route:

```FOR p IN OUTBOUND K_SHORTEST_PATHS 'places/Aberdeen' TO 'places/London'
GRAPH 'kShortestPathsGraph'
LIMIT 3
RETURN {
places: p.vertices[*].label,
travelTimes: p.edges[*].travelTime,
travelTimeTotal: SUM(p.edges[*].travelTime)
}```
```[
{
"places": [
"Aberdeen",
"Leuchars",
"Edinburgh",
"York",
"London"
],
"travelTimes": [
1.5,
1.5,
3.5,
1.8
],
"travelTimeTotal": 8.3
},
{
"places": [
"Aberdeen",
"Leuchars",
"Edinburgh",
"York",
"Carlisle",
"Birmingham",
"London"
],
"travelTimes": [
1.5,
1.5,
3.5,
3.5,
2,
1.5
],
"travelTimeTotal": 13.5
},
{
"places": [
"Aberdeen",
"Leuchars",
"Edinburgh",
"Glasgow",
"Carlisle",
"York",
"London"
],
"travelTimes": [
1.5,
1.5,
1,
1,
2.5,
1.8
],
"travelTimeTotal": 9.3
}
]```

If we ask for routes that don’t exist we get an empty result (from Aberdeen to Toronto):

```FOR p IN OUTBOUND K_SHORTEST_PATHS 'places/Aberdeen' TO 'places/Toronto'
GRAPH 'kShortestPathsGraph'
LIMIT 3
RETURN {
places: p.vertices[*].label,
travelTimes: p.edges[*].travelTime,
travelTimeTotal: SUM(p.edges[*].travelTime)
}```
`[]`

We can use the attribute travelTime that connections have as edge weights to take into account which connections are quicker. A high default weight is set, to be used if an edge has no travelTime attribute (not the case with the example graph). This returns the top three routes with the fewest changes and favoring the least travel time for the connection Saint Andrews to Cologne:

```FOR p IN OUTBOUND K_SHORTEST_PATHS 'places/StAndrews' TO 'places/Cologne'
GRAPH 'kShortestPathsGraph'
OPTIONS {
weightAttribute: 'travelTime',
defaultWeight: 15
}
LIMIT 3
RETURN {
places: p.vertices[*].label,
travelTimes: p.edges[*].travelTime,
travelTimeTotal: SUM(p.edges[*].travelTime)
}```
```[
{
"places": [
"StAndrews",
"Leuchars",
"Edinburgh",
"York",
"London",
"Brussels",
"Cologne"
],
"travelTimes": [
0.2,
1.5,
3.5,
1.8,
2.5,
2
],
"travelTimeTotal": 11.5
},
{
"places": [
"StAndrews",
"Leuchars",
"Edinburgh",
"Glasgow",
"Carlisle",
"Birmingham",
"London",
"Brussels",
"Cologne"
],
"travelTimes": [
0.2,
1.5,
1,
1,
2,
1.5,
2.5,
2
],
"travelTimeTotal": 11.7
},
{
"places": [
"StAndrews",
"Leuchars",
"Edinburgh",
"Glasgow",
"Carlisle",
"York",
"London",
"Brussels",
"Cologne"
],
"travelTimes": [
0.2,
1.5,
1,
1,
2.5,
1.8,
2.5,
2
],
"travelTimeTotal": 12.5
}
]```

And finally clean up by removing the named graph:

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