Search code examples
memgraphdb

Can I use Yen's k-shortest path algorithm in Memgraph?

I am trying to find if there is an implementation of Yen's k-shortest path algorithm in Memgraph and I can't find it in the documentation. Am I missing something or? I am using Memgraph 2.7 and I ran it with Docker.

Solution

  • Currently (Memgraph 2.7), there is no implementation of Yen's k-shortest path algorithm, but there is All shortest paths algorithm in Memgraph that is basically an expansion of a classic Dijkstra's algorithm. If I got it right, for k=1, you need Dijkstra and that's Weighted shortest in Memgraph. With All shortest paths you get k=(all paths). There is a missing part of having k=n, for any number of paths.

    Here is the documentation for Weighted shortest path built-in algorithm in Memgraph (Dijkstra) (k=1 in your case). Here is documentation for All shortest paths (k = all paths in your case).