Advanced traversals

Algorithms

ArangoDB provides a number of built in algorthms for graph traversl including shortest path, all_shortest_paths, k shortest paths Depending upon the alogirth being used, it may return only a vertex, edge or a path comprised of vertexes and edges.

SHORTEST_PATH

1. Lets determine the shortest paths between TPA and SFO
2. To get the shortest path, you can use the following query:

   with airports
   for vertex,edge IN outbound shortest_path  'airports/TPA' to 'airports/SFO' flights
   options {
   weightAttribute: "Distance"
   }
   return edge
3. In this case the only the first route that is found is returned TPA -> ABQ -> SFO

ALL_SHORTEST_PATHS

1. To get all the shortest paths, you can use the following query:

   with airports
   for path IN outbound all_shortest_paths  'airports/TPA' to 'airports/SFO' flights
   options {
   weightAttribute: "Distance"
   }
   return path
2. In this case all the found shortest paths are returned
3. The UI displays the graph visually:

5. You can zoom into the visual to see the name of the nodes

K_SHORTEST_PATHS

1. To get all the k shortest paths, you can use the following query:

   with airports
   for path IN outbound k_shortest_paths  'airports/TPA' to 'airports/SFO' flights
   options {
   weightAttribute: "Distance"
   }
   limit 100
   return path 
2. In this case 100 shortest paths are returned
3. The query without limit could be resource and time intensive trying to explore all possible shortest paths (ordered), we recommend using limits
4. You will see that all the top paths are the same routes (we are currently NOT igoring the schedule)

 

Help us improve

Anything unclear or buggy in this tutorial? Provide Feedback