Neo4j 具有最高聚合关系属性的最短路径

Question

我想找到两个节点之间的最短路径。路径本身不是问题...更大的问题是，我想要返回路径，其中路径上的聚合关系属性最高。

为了更好地理解，这就是我想要的:

这是我的查询

MATCH
  (startNode:Person {id:"887111"}),
  (endNode:Person {id:"789321"}),
  paths = allShortestPaths((startNode)-[r:KNOWS *..20]-(endNode))
RETURN paths

在此示例中，我希望拥有从 Elissa(id:887111)到 Kasey(id:789321)的路径，其中关系上的聚合计数为 MAX。 我还查看了“shortestPath”，它只给了我一条路径。另一种方法是调用“dijkstra”算法，这样我将仅获得“成本”最低(而不是最高)的路径。 因此，在我的示例中，应该显示的唯一路径是 Elissa->Travon->Kasey

我想，问题并不那么复杂，但目前我陷入了困境......

提前致谢。

---

更新

调用建议的查询后

MATCH  (startNode:Person {id:"789321"}), (endNode:Person {id:"887111"}) 
CALL apoc.algo.dijkstra(startNode, endNode, 'KNOWS', '_duration') YIELD path, weight 
RETURN path, -weight AS weight

我的结果如下

Answer 1

[已更新]

我提出了 2 个答案，具体取决于您想要做什么。

1。寻找总权重最大的路径

要找到总权重最大的路径，您可以将原始权重属性的否定输入 Dijkstra 算法。由此产生的“最低”总权重将是一个负值，当取反时，实际上将是最高总权重(基于原始权重属性)。

有一个 APOC 程序，apoc.algo.dijkstra它实现了 Dijkstra 算法，但它不允许您使用指定权重属性的负值。因此，要使用该过程，您需要向每个 KNOWS 关系添加一个具有适当负值的新属性。例如，要将负权重添加到现有关系中(假设 w 是原始权重属性，_w 将包含相应的负值):

MATCH ()-[k:KNOWS]->()
SET k._w = -k.w;

一旦获得负权重，以下内容将为您提供最大权重的路径:

MATCH (startNode:Person {id:"887111"}), (endNode:Person {id:"789321"})
CALL apoc.algo.dijkstra(startNode, endNode, 'KNOWS', '_w') YIELD path, weight
RETURN path, -weight AS weight;

2。从最短路径中选择总权重最大的路径

MATCH
  (startNode:Person {id:"887111"}),
  (endNode:Person {id:"789321"}),
  path = allShortestPaths((startNode)-[:KNOWS *..20]-(endNode))
RETURN path, REDUCE(s = 0, r IN RELATIONSHIPS(path) | s + r.duration) AS weight
ORDER BY weight DESC
LIMIT 1;