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

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

dijkstra traversal neo4j

user1746460 · 技术社区 · 10 年前

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

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

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

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

2 回复 | 直到 10 年前

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)
     }

 }

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