节点之间的neo4j最短路径

Question

我必须找到路径中包含特定类型节点的两个节点之间的最短路径。

有以下密码:

Match p = shortestpath((E1:Entity{seq:"123"}) –[*]-(E2:Entity{seq:"456"})))
Where any(x in nodes(path) where x:T)
Return path

T:标签，可以是百万个节点
dbgraph 大小:4GB

问题是它仅在跳数限制为 5 时才有效，这还不够。

关于如何重写它以进行优化的任何想法？当 6 个或更多跳跃时，它会崩溃。

Answer 1

这种查询的主要问题是在遍历过程中无法截断路径……只有当路径最终以 E2 结束时，您才会知道路径无效，因为这是您可以确定的唯一点路径中的所有节点都不是 :T 节点。

我知道可能会优化一点的唯一方法是确保在达到 E2 时所有扩展都停止，因为现在的查询将找到所有路径，即使是那些扩展超过 E2 的路径，因为可能有一条路径通过E2 ，命中一个 :T 节点，然后最终返回。

不幸的是，这种优化不能用 Cypher 完成。最新版本的 APOC 程序(用于 Neo4j 3.3.x 的 APOC 3.3.0.2 或用于 Neo4j 3.2.x 的 APOC 3.2.3.6)增强了路径扩展程序以与端节点一起工作，我们可以配置扩展以在结束时终止到达节点，因此我们可以停止不必要的扩展(假设通过 E2 然后返回的路径无效)。

MATCH (E1:Entity{seq:"123"}), (E2:Entity{seq:"456"})
CALL apoc.path.expandConfig(E1, {terminatorNodes:[E2]}) YIELD path
WITH path
WHERE any(x in nodes(path) where x:T)
RETURN path
ORDER BY length(path) ASC
LIMIT 1    

虽然这可能会有所帮助(至少在 E2 节点阻止扩展到图的更大部分的情况下)，但对类型没有任何限制且使用 any() 谓词的无界可变长度遍历在大多数情况下不会表现良好由于上述原因，尤其是在不存在此类路径的情况下。