我想弄清楚是否有某种方法可以根据关系总和获得两个节点之间的最短距离,给出这个例子: neo4j image example
上图代码:
CREATE (some_point_1:Point {title:'Some Point 1'})
CREATE (some_point_2:Point {title:'Some Point 2'})
CREATE (some_point_3:Point {title:'Some Point 3'})
CREATE (some_point_4:Point {title:'Some Point 4'})
CREATE (some_point_5:Point {title:'Some Point 5'})
CREATE (some_point_6:Point {title:'Some Point 6'})
CREATE (some_point_1)-[:distance {value:100}]->(some_point_2)
CREATE (some_point_2)-[:distance {value:150}]->(some_point_4)
CREATE (some_point_1)-[:distance {value:200}]->(some_point_3)
CREATE (some_point_3)-[:distance {value:300}]->(some_point_4)
CREATE (some_point_2)-[:distance {value:500}]->(some_point_5)
CREATE (some_point_4)-[:distance {value:300}]->(some_point_5)
CREATE (some_point_5)-[:distance {value:300}]->(some_point_6)
CREATE (some_point_6)-[:distance {value:300}]->(some_point_1)
在此示例中,最短路径应为: some_point_1 > some_point_2 > some_point_4 > some_point_5 (100+150+300 = 550)
Cypher 可以实现这样的功能吗?
最佳答案
Cypher 中的shortestPath
函数不考虑关系属性的累积,因此:
MATCH (start:Point {title: 'Some Point 1'}), (end:Point {title: 'Some Point 5'})
MATCH p=shortestPath((start)-[:distance*]->(end))
RETURN p
会根据路径中的关系数找到从start
到end
的最短路径。
你可以减少距离的总和:
MATCH (start:Point {title: 'Some Point 1'}), (end:Point {title: 'Some Point 5'})
MATCH p=(start)-[:distance*]->(end)
WITH p,reduce(s = 0, r IN rels(p) | s + r.value) AS dist
RETURN p, dist ORDER BY dist DESC
但这里的问题是您需要计算从start
到end
的所有路径的总距离。为了提高效率,您需要使用像 Dijkstra's algorithm 这样的图形搜索算法。或 A*,两者都在 Neo4j's Java API 中实现.
在 Neo4j 3.0 中,这些算法通过 APOC procedure library 在 Cypher 中公开。 .安装 APOC 后,您可以从 Cypher 调用该过程:
MATCH (start:Point {title: 'Some Point 1'}), (end:Point {title: 'Some Point 5'})
CALL apoc.algo.dijkstra(start, end, 'distance', 'value') YIELD path, weight
RETURN path, weight
https://stackoverflow.com/questions/38237237/