Neo4j 具有节点属性的最短路径

Question

我正在尝试在 neo4j 上执行最短路径。然而，我的边缘和节点确实有成本。我想要最小化（节点成本+边缘成本）方面的最短路径。

有办法做到吗？

或者，我必须将节点成本添加到边缘成本中。那么有没有办法动态地做到这一点呢？就像将边缘成本定义为边缘成本=边缘成本+后继节点成本一样。

Answer 1

您可以使用其中一种GDS 路径查找算法 来查找加权最短路径。该算法期望成本是一个关系属性，因此要包含路径中节点的属性，您必须将它们添加为关系属性作为图形投影的一部分（它不会修改数据库中的关系，仅在投影图中）。

这是一个简单的图来说明，其中节点上的成本是属性

e

，关系上的成本是属性

d

：

CREATE (a:A)-[:R {d: 1}]->({e: 2})-[:R {d: 1.5}]->({e: 1.3})-[:R {d: 1}]->(b:B {e: 2}),
       (a)-[:R {d: 1}]->({e: 11})-[:R {d: 1}]->(b)

首先投影一个图，其中关系的属性

cost

是原始关系的

d

与其目标节点的属性

e

之和：

MATCH (source)-[rel]->(target)
RETURN gds.graph.project(
  "example", 
  source, 
  target, 
  { relationshipProperties: { cost: rel.d + target.e } }
) AS g

作为示例，以下是如何使用 Dijkstra 获取具有标签

A

的节点和具有标签

B

的节点之间的最短距离：

MATCH (source:A), (target:B)
CALL gds.shortestPath.dijkstra.stream(
  "example", 
  {
    sourceNode: source, 
    targetNode: target, 
    relationshipWeightProperty: "cost"
  }
)
YIELD path
RETURN path