dgraph icon indicating copy to clipboard operation
dgraph copied to clipboard

a little performance improve on k-shortest

Open BlankRain opened this issue 5 years ago • 3 comments

https://discuss.dgraph.io/t/performance-is-not-good-when-finding-the-paths-between-2-nodes-with-k-shortest/3533/2 https://discuss.dgraph.io/t/shortest-query-runs-out-memory/3695

If the data has cycle , for example A to B , to is a reversed edge. so B ~to A. if there is a path A to B to C to D . it may add some route like A to B ~to A to B to C to D. the cycling in A to B ~to A wastes memory. and make the priorityQueue growing without stop. that's one of the reasons for run out of memory. In Djikstras algorithm , a DAG is better. so if we break some cycles in adjacencyMap, we can make our path-finder go forward. and save half of memory if A B both connected as A to B, B ~to A


This change is Reviewable

BlankRain avatar Dec 05 '19 10:12 BlankRain

CLA assistant check
Thank you for your submission! We really appreciate it. Like many open source projects, we ask that you sign our Contributor License Agreement before we can accept your contribution.
You have signed the CLA already but the status is still pending? Let us recheck it.

CLAassistant avatar Apr 29 '22 07:04 CLAassistant