neo4j 最短路径算法
neo4j shortestPath algorithm
我对 neo4j 中的 shortestPath 算法有疑问。
如果我有一个有10^6个节点的图，每个节点有1000个关系，搜索最多4层的最短路径，必须搜索1000*1000*1000*1000=10^12个更高的节点比总节点。原因是在搜索过程中有些节点是重复的。我的问题是，在 neo4j shortestPath 算法中，此搜索需要时间来接触 10^6 个节点或 10^12 个节点。换句话说，它是否标记已经搜索过的节点以不再搜索它们？
谢谢
我不相信使用了那种修剪。在 Cypher 中，遍历的默认唯一性是 RELATIONSHIP_PATH：在每个路径中，关系必须是唯一的，它们不能重复使用。
您可以尝试使用 Graph Algorithms project or one of APOC Procedures' path expander procs 中的 shortestPath proc。
使用 APOC 路径扩展器，您可以自己将唯一性设置为 NODE_GLOBAL（这样可以防止在所有扩展过程中多次处理相同的节点），或者使用已经在引擎盖（subgraphNodes()、subgraphAll() 或 spanningTree()）。
APOC 的问题（目前）是您目前无法提供扩展的末端节点（您必须扩展到具有特定定义标签的节点，然后使用 WHERE 过滤结果子句），并且扩展仅沿一个方向（从起始节点向外）而不是双向（例如从 cypher 的 shortestPath()）进行，因此您不会意识到从另一个方向扩展可能带来的任何效率改进。
我目前在 APOC 上有一个 PR 来提供扩展的已知终端节点，所以它应该会进入下一个 APOC 版本（在下周左右）。
我对 neo4j 中的 shortestPath 算法有疑问。
如果我有一个有10^6个节点的图，每个节点有1000个关系，搜索最多4层的最短路径，必须搜索1000*1000*1000*1000=10^12个更高的节点比总节点。原因是在搜索过程中有些节点是重复的。我的问题是，在 neo4j shortestPath 算法中，此搜索需要时间来接触 10^6 个节点或 10^12 个节点。换句话说，它是否标记已经搜索过的节点以不再搜索它们？
谢谢
我不相信使用了那种修剪。在 Cypher 中，遍历的默认唯一性是 RELATIONSHIP_PATH：在每个路径中，关系必须是唯一的，它们不能重复使用。
您可以尝试使用 Graph Algorithms project or one of APOC Procedures' path expander procs 中的 shortestPath proc。
使用 APOC 路径扩展器，您可以自己将唯一性设置为 NODE_GLOBAL（这样可以防止在所有扩展过程中多次处理相同的节点），或者使用已经在引擎盖（subgraphNodes()、subgraphAll() 或 spanningTree()）。
APOC 的问题（目前）是您目前无法提供扩展的末端节点（您必须扩展到具有特定定义标签的节点，然后使用 WHERE 过滤结果子句），并且扩展仅沿一个方向（从起始节点向外）而不是双向（例如从 cypher 的 shortestPath()）进行，因此您不会意识到从另一个方向扩展可能带来的任何效率改进。
我目前在 APOC 上有一个 PR 来提供扩展的已知终端节点，所以它应该会进入下一个 APOC 版本（在下周左右）。