mongoDB, 노드 JS 및 최단 경로 기능, 모든 옵션을 사용할 수 있습니까?

Question

직장에서 Node JS + Mongo DB (몽구스)에 기반한 위치 애플리케이션을 유지 관리하고 있습니다. 우리가 필요로했던 지오 로케이션 기능은 이미 매우 간단하고 MongoDB에서 이미 사용 가능합니다 ($ near, $ geoWithin 및 $ geoIntersect). 우리의 주요 문제는 방금 요구 사항과 함께, 우리가 저장 한 일부 위치 사이의 최적의 경로를 확인하는 "최단 경로"기능을 사용해야합니다.

인터넷에서 보거나 검색하는 것은 mongo가 최단 경로 기능을 갖고 있지 않은 것으로 보이며 일부 기사는이 작업 (neo4j 또는 postgis)을 수행하기 위해 두 번째 데이터베이스를 처리 할 것을 제안합니다.

질문은 몽고와 노드만으로 최단 경로 기능을 구현할 수있는 저렴한 방법이 있습니까? 또는 두 번째 데이터베이스를 처리하는 경우 가장 좋은 조합이 될 수 있습니까?

UPDATE는 최근에 나는 최단 경로를 추적하는 데 유용 할 수있는 방법에 대해 이야기를 충족 몽고 DB 유럽 16, 몽고 DB 3.4에서 $ graphLookup 기능을 발견했다. 현재이 기능이 내가 원하는 것을 얻기위한 적절한 기능입니까?

Answer 1

mongodb에서 최단 경로 계산을 수행하는 원시 연산이 없습니다.

별도의 그래프 데이터 저장소 구현, 유지 관리 및 동기화 비용을 피하고 그래프의 크기가 너무 크지 않은 경우 노드, 에지 및 가중치 (또는 거리)를 메모리에로드하고 자바 스크립트에서 최단 경로 계산.

은 당신이 모든 가장자리에 대한 가중치를 제공하는 그래프를 초기화 한 후 path 함수를 호출 할 필요가 노드 dijstra 문서에 따르면 node-dijkstra

와 같은 라이브러리를 사용하여 자신을 최단 경로 알고리즘을 구현하지 않도록합니다.

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' ]