Neo4j中没有超节点的最短路径

Question

我有一个在Neo中有5亿个节点和边缘的图表.我想找到2个节点之间的最短路径,避免超级节点(即使它比它们上面有超级节点的路径长).

以下查询适用于较小的图形,但永远不会完成我正在处理的大小的图形:

MATCH (n:Node { id:'123'}),(m:Node { id:'234' }), p = shortestPath((n)-[*..6]-(m)) 
WHERE NONE(x IN NODES(p) WHERE size((x)--())>1000)
RETURN p

如果我删除WHERE子句,它是超级快的.通常是亚秒级.

我怎样才能加快速度？预先计算节点度数和索引它们会有帮助吗？我是否应该重复除了与超级节点相邻的边缘之外的所有边缘,为它们提供一个新标签并将它们用于我的shortestPath查询而不使用WHERE子句？还有其他建议吗？

Answer 1

据我所知，当 WHERE ALL 仅包含关系（而不是节点）时，Neo4j 最短路径实现会修剪路径。如果它无法修剪查询，它会找到所有路径，然后过滤它们（慢）。

正如马丁所说，你可以添加一个标签：

MATCH (x:Node)
WHERE size((x)--())>1000
SET n:Supernode

然后通过边询问节点的标签：

MATCH p = shortestPath((n:Node { id:'1'})-[*..6]-(m:Node { id:'2' })) 
WHERE ALL( rel IN relationships(p) WHERE not (startNode(rel):Supernode or endNode(rel):Supernode))
RETURN p

这将允许 Neo4j 使用优化的、双向的、广度优先（快速）查询。

更多内容请阅读： https://neo4j.com/docs/developer-manual/current/cypher/execution-plans/shortestpath-planning/