在 arangodb 中查找通过预定义顶点和边集的最短路径

Question

我需要找到应该通过多个节点和边的最短路径。几个细节：

1. 根据权重，它应该是最短路径。
2. 包括集可以是有序的和无序的。
3. 图形大小 - 50 000 个顶点和 450 0000 条边

有没有办法使用 arangodb 找到这样的路径？ 我已经尝试过K_SHORTEST_PATHS但在某些情况下太慢了。

Answer 1

如果没有数据集，这很难测试。 不幸的是，K_SHORTEST_PATHS是向边缘添加"权重"的唯一内置方法，除非您自己构建某些东西。 此外，两种SHORTEST_PATH方法都没有实现PRUNE，这是加速图遍历的最佳方法。

我的建议是使用有向图方法(FOR v,e,p IN 1..9 INBOUND x...(，实现PRUNE和FILTER子句以减少跃点数，以及类似COLLECT path = p AGGREGATE weight = SUM(e.weight)来计算权重。