Найти кратчайшие пути через предопределенный набор вершин и ребер в 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) для расчета веса.