The AQL feature k Shortest Paths allows you to query not just a shortest path between two documents in an ArangoDB database, but the list of paths between them, sorted by length, or weight.

To walk you through how to use this feature, we will setup a small graph that represents train connections in Europe, giving travel time as weight on each edge, and then query for some short connections using k Shortest Paths queries in AQL.

See a quick feature overview here:

Create a new graph TrainGraph with document collection places, and an edge collection connections;

and copy and paste the following two queries to setup the example graph

We can now explore the resulting graph in ArangoDB’s graph viewer:

Suppose we want to plan a trip from Leuchars to Cologne. If we want to know which connection has the fewest stations, we could use the following query:

which gives the connection Leuchars, Edinburgh, York, London, Brussels, Cologne. We can obtain the same result by using K_SHORTEST_PATHS with LIMIT 1, which restricts the result to one returned path:

Note that K_SHORTEST_PATHS returns every path as a JSON object with components vertices, edges, and weight.

Increasing the LIMIT will give alternative routes that might be a little longer than the shortest route, for example

Here, we also get Leuchars, Edinburgh, York, Carlisle, Birmingham, London, Brussels, Cologne, and*Leuchars, Edinburgh, Glasgow, Carlisle, Birmingham, London, Brussels, Cologne.

What if we want to take travel time into account? We can tell K_SHORTEST_PATHS the name of an attribute that contains the travel time!

Which returns the routes Leuchars, Edinburgh, York, London, Brussels, Cologne with weight 11.3,
Leuchars, Edinburgh, Glasgow, Carlisle, Birmingham, London, Brussels, Cologne with weight 11.5, and
Leuchars, Edinburgh, York, Carlisle, Birmingham, London, Brussels, Cologne with weight 12.3.

Should we try planning a route that does not exist, such as a trip from London to Toronto

We can get lucky and get the answer that there is no such route quickly, but we might also have to wait for a long time for ArangoDB to conclude that there is no such path: It might have to search the whole of the European train network, and the whole of the Canadian train network, to find that there is no train connection between those two.

k Shortest Paths are a useful tool when you want to query your graph database for alternative paths to the shortest path that are just deviating a bit in terms of cost.

The K_SHORTEST_PATHS keyword also supports the INBOUND and ANY modifier to specify which direction edges should be considered in. You can find its documentation here.