最短路径规划
此页面包含使用 shortestPath() 函数规划查询的示例。
在 Cypher® 中规划最短路径会导致不同的查询计划，具体取决于需要评估的谓词。在内部，Neo4j 将使用快速双向广度优先搜索算法，如果可以在搜索路径时评估谓词。因此，当路径上存在通用谓词时，这种快速算法将始终能够返回正确的结果；例如，当搜索所有节点都具有 Person 标签的最短路径，或者路径上没有具有 name 属性的节点时。
如果谓词需要在决定路径是否有效之前检查整个路径，那么这种快速算法无法依赖于找到最短路径，Neo4j 可能不得不诉诸使用更慢的穷尽深度优先搜索算法来查找路径。这意味着具有非通用谓词的最短路径查询的查询计划将包括一个回退，即在快速算法未成功的情况下运行穷尽搜索以查找路径。例如，根据数据，具有存在谓词的最短路径查询的答案（例如，要求至少一个节点包含属性 name='Kevin Bacon'）可能无法通过快速算法找到。在这种情况下，Neo4j 将回退到使用穷尽搜索来枚举所有路径并可能返回答案。
这两种算法的运行时间可能相差几个数量级，因此确保为时间敏感的查询使用快速方法非常重要。
当计划穷尽搜索时，它仍然只在快速算法未能找到任何匹配路径时执行。快速算法始终先执行，因为有可能即使在计划时无法保证，它也能找到有效的路径。
请注意，在某些情况下，回退到穷尽搜索可能会证明是一种非常耗时的策略；例如，当两个节点之间没有最短路径时。因此，在这些情况下，建议将 cypher.forbid_exhaustive_shortestpath 设置为 true，如 操作手册 → 配置设置 中所述。
最短路径 - 快速算法
示例 1. 使用快速算法评估的查询
此查询可以使用快速算法进行评估 - 没有需要在评估之前查看整个路径的谓词。
查询
PROFILE
MATCH
(KevinB:Person {name: 'Kevin Bacon'}),
(Al:Person {name: 'Al Pacino'}),
p = shortestPath((KevinB)-[:ACTED_IN*]-(Al))
WHERE all(r IN relationships(p) WHERE r.role IS NOT NULL)
RETURN p查询计划
Planner COST Runtime PIPELINED Runtime version 5.25 Batch size 128 +---------------------+------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+ | Operator | Details | Estimated Rows | Rows | DB Hits | Memory (Bytes) | Page Cache Hits/Misses | Time (ms) | Pipeline | +---------------------+------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+ | +ProduceResults | p | 2 | 1 | 0 | | 1/0 | 0.252 | | | | +------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+ | | +ShortestPath | p = (KevinB)-[anon_0:ACTED_IN*]-(Al) WHERE all(r IN relationships(p) WHERE r.role IS NOT NULL) | 2 | 1 | 23 | 1688 | | | In Pipeline 1 | | | +------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+ | +MultiNodeIndexSeek | RANGE INDEX KevinB:Person(name) WHERE name = $autostring_0, | 2 | 1 | 4 | 120 | 1/1 | 0.916 | In Pipeline 0 | | | RANGE INDEX Al:Person(name) WHERE name = $autostring_1 | | | | | | | | +---------------------+------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+ Total database accesses: 27, total allocated memory: 1752
最短路径 - 对路径的附加谓词检查
在 WHERE 子句中使用的适用于最短路径模式的谓词在决定最短匹配路径之前进行评估。
示例 2. 考虑使用穷尽搜索作为回退
查询
MATCH
(KevinB:Person {name: 'Kevin Bacon'}),
(Al:Person {name: 'Al Pacino'}),
p = shortestPath((KevinB)-[*]-(Al))
WHERE length(p) > 1
RETURN p与上面的查询相比，此查询需要检查整个路径是否遵循谓词，然后我们才知道它是否有效，因此查询计划也将包括回退到更慢的穷尽搜索算法。
查询计划
Planner COST
Runtime PIPELINED
Runtime version 5.25
Batch size 1024
+--------------------------+-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| Operator | Details | Estimated Rows | Rows | DB Hits | Memory (Bytes) | Page Cache Hits/Misses | Time (ms) | Pipeline |
+--------------------------+-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| +ProduceResults | p | 1 | 1 | 0 | | | | |
| | +-------------------------------------------------------------+----------------+------+---------+----------------+ | | |
| +AntiConditionalApply | | 1 | 1 | 0 | 41464 | 0/0 | 0.332 | Fused in Pipeline 6 |
| |\ +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| | +Top | anon_1 ASC LIMIT 1 | 2 | 0 | 0 | 4280 | 0/0 | 0.000 | In Pipeline 5 |
| | | +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| | +Projection | length(p) AS anon_1 | 7966 | 0 | 0 | | | | |
| | | +-------------------------------------------------------------+----------------+------+---------+----------------+ | | |
| | +Filter | length(p) > $autoint_2 | 7966 | 0 | 0 | | | | |
| | | +-------------------------------------------------------------+----------------+------+---------+----------------+ | | |
| | +Projection | (KevinB)-[anon_0*]-(Al) AS p | 26554 | 0 | 0 | | | | |
| | | +-------------------------------------------------------------+----------------+------+---------+----------------+ | | |
| | +VarLengthExpand(Into) | (KevinB)-[anon_0*]-(Al) | 26554 | 0 | 0 | | | | |
| | | +-------------------------------------------------------------+----------------+------+---------+----------------+ | | |
| | +Argument | KevinB, Al | 2 | 0 | 0 | 0 | 0/0 | 0.000 | Fused in Pipeline 4 |
| | +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| +Apply | | 2 | 1 | 0 | | 0/0 | 0.026 | |
| |\ +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| | +Optional | KevinB, Al | 2 | 1 | 0 | 4840 | 0/0 | 0.134 | In Pipeline 3 |
| | | +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| | +ShortestPath | p = (KevinB)-[anon_0*]-(Al) WHERE length(p) > $autoint_2 | 1 | 1 | 1 | 1760 | | | In Pipeline 2 |
| | | +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| | +Argument | KevinB, Al | 2 | 1 | 0 | 24680 | 0/0 | 0.056 | In Pipeline 1 |
| | +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| +MultiNodeIndexSeek | RANGE INDEX KevinB:Person(name) WHERE name = $autostring_0, | 2 | 1 | 4 | 120 | 2/0 | 0.644 | In Pipeline 0 |
| | RANGE INDEX Al:Person(name) WHERE name = $autostring_1 | | | | | | | |
+--------------------------+-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
Total database accesses: 5, total allocated memory: 50152较大的穷尽查询计划的工作方式是使用 Apply/Optional 来确保当快速算法没有找到任何结果时，生成一个 null 结果，而不是简单地停止结果流。除此之外，计划程序将发出一个 AntiConditionalApply，如果路径变量指向 null 而不是路径，它将运行穷尽搜索。
在以下情况下，执行计划中将出现 ErrorPlan 运算符
-
dbms.cypher.forbid_exhaustive_shortestpath设置为true。 -
快速算法无法找到最短路径。
示例 3. 阻止穷尽搜索用作回退
查询
MATCH
(KevinB:Person {name: 'Kevin Bacon'}),
(Al:Person {name: 'Al Pacino'}),
p = shortestPath((KevinB)-[*]-(Al))
WITH p
WHERE length(p) > 1
RETURN p此查询与上面的查询类似，需要检查整个路径是否遵循谓词，然后我们才知道它是否有效。但是，包含 WITH 子句意味着查询计划将不包括回退到更慢的穷尽搜索算法。相反，快速算法找到的任何路径随后将被过滤，这可能导致没有答案返回。
查询计划
Planner COST
Runtime PIPELINED
Runtime version 5.25
Batch size 128
+---------------------+-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+
| Operator | Details | Estimated Rows | Rows | DB Hits | Memory (Bytes) | Page Cache Hits/Misses | Time (ms) | Pipeline |
+---------------------+-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+
| +ProduceResults | p | 1 | 1 | 0 | | 1/0 | 0.353 | |
| | +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+ |
| +Filter | length(p) > $autoint_2 | 1 | 1 | 0 | | 0/0 | 0.255 | |
| | +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+ |
| +ShortestPath | p = (KevinB)-[anon_0*]-(Al) | 2 | 1 | 1 | 1760 | | | In Pipeline 1 |
| | +-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+
| +MultiNodeIndexSeek | RANGE INDEX KevinB:Person(name) WHERE name = $autostring_0, | 2 | 1 | 4 | 120 | 2/0 | 0.371 | In Pipeline 0 |
| | RANGE INDEX Al:Person(name) WHERE name = $autostring_1 | | | | | | | |
+---------------------+-------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+
Total database accesses: 5, total allocated memory: 1824