CouchDB 图形中的最短路径

Question

我正在尝试计算存储在 CouchDB 中的图形中的最短路径。我必须在 db 中执行此操作，因为我的任务是比较 3 种不同 DBMS 在各种情况下的查询速度。因此，在 python（或其他任何东西）中加载数据和运行 dijkstra 不是一种选择。我对基于文档的数据库很陌生，所以我可能错了，但在我看来，我唯一的选择是视图。

我的数据库结构如下：

• 一份文件代表一张图。

• 在带有“边缘”键的文档中，有一组具有 3 个属性的对象：开始、结束、距离。

• start和end是节点 ID，但没有关于节点的其他有趣信息，因此它们不会存储在其他任何地方。

• 距离是一个浮动

我的想法是创建一个返回最短路径的视图。我有计算它的代码。它基于这篇文章。我只需要稍微修改一下，否则我会遇到像let,foreach这样的语法错误：

function (doc) {

  function Graph() {

    this.nodes = [];

    this.adjacencyList = {};

    this.addNode = function(node) {

      if(this.nodes.indexOf(node) != -1)

        return;

      this.nodes.push(node); 

      this.adjacencyList[node] = [];

    }

    this.addEdge = function(node1, node2, weight) {

      this.adjacencyList[node1].push({node:node2, weight: weight});

      //this.adjacencyList[node2].push({node:node1, weight: weight});

    }

    this.shortestPath = function(startNode, endNode){

      var times = {};

      var backtrace = {};

      var pq = new PriorityQueue();

      times[startNode] = 0;

      for(var i = 0; i<this.nodes.length; i++){

        if(this.nodes[i] != startNode){

          times[node] = Infinity;

        }

      }

      pq.enqueue([startNode, 0]);

      while (!pq.isEmpty()) {

        var shortestStep = pq.dequeue();

        var currentNode = shortestStep[0];

        for(var i=0;i< this.adjacencyList[currentNode].length; i++){

          var neighbor = this.adjacencyList[currentNode][i];

          var time = times[currentNode] + neighbor.weight;

          if (time < times[neighbor.node]) {

            times[neighbor.node] = time;

            backtrace[neighbor.node] = currentNode;

            pq.enqueue([neighbor.node, time]);

          }

        }

      }

      var path = [endNode];

      var lastStep = endNode;

      while(lastStep !== startNode) {

        path.unshift(backtrace[lastStep]);

        lastStep = backtrace[lastStep];

      }

      return 'Path is ${path} and time is ${times[endNode]}';

    }

  };

但是，在查询视图时，我得到 0 行。

Answer 1

终于我找到了。当我将 foreach 重写为传统的 for 时，我忘记更改了：for(var i = 0; i<this.nodes.length; i++){&nbsp; &nbsp; if(this.nodes[i] != startNode){&nbsp; &nbsp; &nbsp; times[node] = Infinity;&nbsp; &nbsp; }}对此：for(var i = 0; i<this.nodes.length; i++){&nbsp; &nbsp;if(this.nodes[i] != startNode){&nbsp; &nbsp; &nbsp; times[this.nodes[i]] = Infinity;&nbsp; &nbsp;}}有趣的是，我在 CouchDB 中没有看到任何错误。我必须使用 node.js 在本地运行我的代码才能发现有错误。