Neo4j - 根据关系属性查找两个节点之间的最短路径

Question

我试图弄清楚是否有一些基于关系总和获得两个节点之间的最短距离,给出了这个例子: neo4j图像示例

上图代码:

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可以这样吗？

Answer 1

shortestPathCypher中的函数没有考虑关系属性的累积,因此:

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算法或A*这样的图搜索算法,这两种算法都是在Neo4j的Java API中实现的.

在Neo4j 3.0中,这些算法通过APOC过程库在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