Performance is not good when finding the paths between 2 nodes with k-shortest


Hi there,
I tried to find paths between 2 nodes, currently only k-shortest path queries could be used, the performance was not good when i queried with numpaths larger than 10.
Is there any suggestion on that ?
Why the performance lose a lot when numpaths become larger?
Why the performance changed with depth 10?
Any way to improve it?

I used the dgraph-ha.yaml to deploy my dgraph
and here’s my ql to query
path as shortest(from: 0x107db5, to: 0x138ac1, numpaths:10) {
path(func: uid(path)) {

here’s the results:
10<=numpaths<=20 : 9.5s to 10s
numpaths<10 : 100 to 300ms

BTW, i used the HDD for this test



k-shortest paths is not a particularly cheap calculation. Yen’s
algorithm (I don’t know if dgraph uses this, but it likely uses
something similar - it does look much more complicated than it needs to
be though) has a time complexity of O(k|V|(|E|+|V|log|V|)).


hi kortschark, thanks for your reply. With the time complexity, it should cost more time with larger k. But by my testing, the time didn’t change a lot when i changed the k to 10 or larger, it looks very strange. Do you have any idea on that?


I’ve just had a closer look at the code, and despite the illegibility of it it’s reasonably clear that they are not using Yan, though they are doing similar work less efficiently.

I can’t see any discontinuity at 10 unless it’s something in the runtime (grow map?, though that seems unlikely) or something to do with the backing store (more likely).


thanks for your info, i’ll try to find if there’s some limitation on the backing store