mongoDB, узел JS и функция кратчайшего пути, доступна любая опция?

Question

На работе мы поддерживаем приложение местоположения, основанное на узле JS + Mongo DB (Mongoose). Необходимые геолокационные функции были очень простыми и доступны уже в MongoDB ($ near, $ geoWithin и $ geoIntersect). Наша основная проблема только пришла с требованиями, нужно ли нам использовать функцию «кратчайшего пути», чтобы проверять лучшие маршруты между некоторыми местами, которые мы получили.

Поиск и поиск в Интернете, похоже, что у mongo нет функции кратчайшего пути, и в некоторых статьях предлагается использовать вторую базу данных для выполнения этой задачи (neo4j или postgis).

Вопрос в том, что существует доступный способ достижения кратчайшего пути с помощью монго и узла? или если дело со второй базой данных, что может быть лучшей комбинацией ?.

UPDATE

Недавно я нашел функцию $ graphLookup в Монго DB 3.4, в Mongo Db Европе 16 встречаются переговоры о том, как может быть полезно для отслеживания кратчайшего пути. Является ли это в настоящее время подходящей функцией для достижения того, что я ищу?

Answer 1

В mongodb нет встроенной операции, которая вычисляет кратчайший путь.

Если вы хотите избежать затрат на реализацию, обслуживание и синхронизацию отдельного хранилища данных графа, и если размер графика не является чрезмерно большим, вы можете загрузить узлы, ребра и веса (или расстояния) в память и выполнить кратчайший путь в javascript.

Чтобы избежать реализаций кратчайшего алгоритма пути самостоятельно вы можете использовать библиотеку, такую ​​как node-dijkstra

Согласно узлу dijstra документации вам необходимо инициализировать график предоставления весов для каждого ребра, а затем вызвать функцию path.

const Graph = require('node-dijkstra') 

const route = new Graph() 

route.addNode('A', { B:1 }) 
route.addNode('B', { A:1, C:2, D: 4 }) 
route.addNode('C', { B:2, D:1 }) 
route.addNode('D', { C:1, B:4 }) 

route.path('A', 'D') // => [ 'A', 'B', 'C', 'D' ]