Neo4j-根据关系属性查找两个节点之间的最短路径 [英] Neo4j - Finding the Shortest Path between two nodes based on relationship property

问题描述

在此示例中，我试图确定是否有某种方法可以根据关系总和获得两个节点之间的最短距离: neo4j图片示例

I'm trying to figure out if there's someway to get the shortest distance between two nodes based in a relationship sum, given this example: 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)

In this example the shortest path should be: some_point_1 > some_point_2 > some_point_4 > some_point_5 (100+150+300 = 550)

Cypher可以实现这种功能吗?

Is something like this possible with Cypher?

推荐答案

Cypher中的shortestPath函数未考虑关系属性的累积，因此:

The shortestPath function in Cypher does not take into account accumulating of relationship properties, so this:

MATCH (start:Point {title: 'Some Point 1'}), (end:Point {title: 'Some Point 5'})
MATCH p=shortestPath((start)-[:distance*]->(end))
RETURN p

将根据路径中的关系数找到从start到end的最短路径.

would find the shortest path from start to end based on the number of relationships in the path.

您可以减少距离的总和:

You could reduce on the sums of the distances:

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中实现.

But the problem here is that you need to calculate the total distance for all paths from start to end. To be more efficient you want to use a graph search algorithm like Dijkstra's algorithm or A*, both of which are implemented in Neo4j's Java API.

在Neo4j 3.0中，这些算法通过 APOC过程库在Cypher中公开.安装APOC后，您可以从Cypher调用该过程:

In Neo4j 3.0 these algorithms are exposed in Cypher through the APOC procedure library. Once you install APOC you can call the procedure from 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

这篇关于Neo4j-根据关系属性查找两个节点之间的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！