Hey Fauna-Community,

is it possible to use Fauna for shortest path queries?

I’m looking at the social graph example from the docs which has some details on direct link queries. I’m trying to achieve a query like this: “What is the shortest path between Dave and Bob?” => Dave->Alice->Bob.

This is a shortest path problem in graphs. I’m thinking of running Dijkstra in a Fauna Function. Is this performant?

Next to shortest-path, I’d also be interested in k-shortest-path.

Cheers, Anton

2 Likes

Hi @abegehr - welcome to the forums!

I’m going to set k-shortest aside, as I only learned about it from your post. That said, you *should* be able to get there from my understanding.

The key to Dijkstra in FQL is recursion with user-defined functions (UDFs). Keep in mind the following constraints:

- You must pass the set of visited nodes into each recursive call. This grows linearly
*per individual potential path*but*exponentially*for the overall calculation. Quite frankly, I’m not sure how this will affect performance. You will need to test/measure to be sure. -
Recursive calls in FQL are limited to a depth of 200, which in turn will limit the maximum search path length. Note that there’s no limitation on
*width*, so if each node has thousands of edges, I’m again uncertain about what will happen.

The basic format of recursion is:

```
CreateFunction({
name: "ShortestPath",
body: Query(Lambda(
["graph", "source"],
Map(
Select(["nodes"], Var("graph")),
Lambda(
"nextNode",
Call(
"ShortestPath",
[Var("nextNode"), Var("source")]
)
)
)
))
})
```

**Note:** This is *not* an attempt to implement Dijkstra or even what your signature will look like, only an example to show you how recursion is implemented in UDFs.

There’s a lot more to do here. Let us know how this turns out!