最短路径规划
此页面包含一个示例，说明如何使用 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 2025.05 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 2025.05
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 2025.05
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