代码之家  ›  专栏  ›  技术社区  ›  user1746460

基于路径权重和节点财产dijkstra的遍历

  •  0
  • user1746460  · 技术社区  · 10 年前

    在检查节点上的某些财产的同时,能否找到节点a和B之间的最小开销路径?

    例如,我想找到从A到B的最短公交路线,其中链接的权重是距离。因此,路径不仅应该成本最低,而且路径上的节点应该有一个公共汽车站/站。

    因此,返回的路径是所有节点都作为公交站点的最低成本路径(假设属性bus_stop=yes)。

    TraversalDescription提供评估器,可以在其中检查节点财产。Dijkstra也有类似的可能吗?

    2 回复  |  直到 10 年前
        1
  •  1
  •   Stefan Armbruster    8 年前

    使用Neo4j时 graphalgo 包装,您需要提供自定义 CostEvaluator Dijkstra算法。不要只使用旅行时间(也称为关系属性),您应该返回旅行时间(关系属性)加上在公共汽车站的等待时间(节点属性)的总和:

     class BusCostEvaluator implements CostEvaluator<Float> {
    
         public Float getCost(Relationship r, Direction d) {
             return (Float)r.getStartNode().getProperty("waitTime", 0f) +
                 (Float)r.getProperty("travelTime", 0f)
         }
    
     }
    
        2
  •  0
  •   Sumeet Sharma    10 年前

    请尝试以下查询。它假设所有链接都有一个属性权重,并将路径权重和长度组合相加,以对结果排序。它首先只过滤所有节点bus_stop为yes的路径

    MATCH p=a-[r*]->b
    WHERE all(x1 in nodes(p) where x1.bus_stop = 'yes')
    WITH extract(link IN r| link.weight) AS wts, length(p) AS len
    RETURN wts, reduce(sum=0, x IN wts| sum+x) AS totalwt, len
    order by totalwt