最短路径

Cypher® 关键字 SHORTEST 用于查找节点间各种形式的最短路径。这包括查找最短路径、次短路径（以此类推）、所有可用的最短路径，以及包含相同模式长度的路径组。文中还介绍了可用于测试给定节点间可达性的 ANY 关键字，以及如何在使用 SHORTEST 的查询中应用过滤器。

SHORTEST 在功能上取代并扩展了 shortestPath() 和 allShortestPaths() 函数。这两个函数仍可使用，但它们不符合 GQL 标准。有关详细信息，请参阅语法与语义 → shortestPath() 和 allShortestPaths() 函数。

关于 Cypher 和 GDS 最短路径的说明

Cypher 和 Neo4j 的图数据科学 (GDS) 库都可以用来查找节点间各种形式的最短路径。

在以下情况使用 Cypher：

您需要通过量化路径模式指定复杂的图导航。
创建图投影 (graph projection) 所需时间过长。
您的实例中无法使用 GDS，或者 GDS 投影的大小对于您的实例来说过大。

在以下情况使用 GDS：

您需要计算加权最短路径。
您需要特定的算法，如 A* 或 Yen’s 算法。
在查找最短路径之前，您需要先通过投影转换图。
您需要在流水线中将最短路径与其他 GDS 算法结合使用。

要阅读有关 GDS 库中包含的最短路径算法的更多信息，请参阅 GDS 图算法 → 路径查找。

`SHORTEST k`

本节使用以下图表

要重新创建它，请在空的 Neo4j 数据库中运行以下查询

CREATE (asc:Station {name:"Ashchurch"}),
  (bmv:Station {name:"Bromsgrove"}),
  (cnm:Station {name:"Cheltenham Spa"}),
  (dtw:Station {name:"Droitwich Spa"}),
  (hby:Station {name:"Hartlebury"}),
  (psh:Station {name:"Pershore"}),
  (wop:Station {name:"Worcestershire Parkway"}),
  (wof:Station {name:"Worcester Foregate Street"}),
  (wos:Station {name:"Worcester Shrub Hill"})
CREATE (asc)-[:LINK {distance: 7.25}]->(cnm),
  (asc)-[:LINK {distance: 11.29}]->(wop),
  (asc)-[:LINK {distance: 14.75}]->(wos),
  (bmv)-[:LINK {distance: 31.14}]->(cnm),
  (bmv)-[:LINK {distance: 6.16}]->(dtw),
  (bmv)-[:LINK {distance: 12.6}]->(wop),
  (dtw)-[:LINK {distance: 5.64}]->(hby),
  (dtw)-[:LINK {distance: 6.03}]->(wof),
  (dtw)-[:LINK {distance: 5.76}]->(wos),
  (psh)-[:LINK {distance: 4.16}]->(wop),
  (wop)-[:LINK {distance: 3.71}]->(wos),
  (wof)-[:LINK {distance: 0.65}]->(wos)

通过路径模式匹配的路径可以通过包含关键字 SHORTEST k 来限制为仅查找最短路径（按跳数计算），其中 k 是要匹配的路径数量，既可以是 INTEGER 字面量，也可以是（自 Neo4j 2025.06 起）解析为 INTEGER 的参数。例如，以下示例使用 SHORTEST 1 来返回 Worcester Shrub Hill 和 Bromsgrove 之间的最短路径长度

查询

MATCH p = SHORTEST 1 (wos:Station)-[:LINK]-+(bmv:Station)
WHERE wos.name = "Worcester Shrub Hill" AND bmv.name = "Bromsgrove"
RETURN length(p) AS result

请注意，本节的此示例及后续示例使用了量化关系 -[:LINK]-+，它由关系模式 -[:LINK]- 和后缀量词 + 组成。该关系模式仅关注类型为 LINK 的关系，除此之外会遍历沿途的任何节点。关系模式上没有箭头 < 或 >，允许模式匹配任一方向的关系。这反映了火车可以在站点之间的 LINK 关系上双向运行的事实。+ 量词表示应匹配一个或多个关系。有关详细信息，请参阅语法与语义 - 量化关系。

结果
结果
`2`
行：1

尽管查询仅返回了一个结果，但实际上有两条路径并列为最短路径

由于 SHORTEST 中指定了 1，因此只返回其中一条路径。返回哪一条是不确定的。

如果改为指定 SHORTEST 2，则本例中的所有最短路径都将被返回，结果将是确定性的

查询

MATCH p = SHORTEST 2 (wos:Station)-[:LINK]-+(bmv:Station)
WHERE wos.name = "Worcester Shrub Hill" AND bmv.name = "Bromsgrove"
RETURN [n in nodes(p) | n.name] AS stops

结果
经停站
`["Worcester Shrub Hill", "Droitwich Spa", "Bromsgrove"]`
`["Worcester Shrub Hill", "Worcestershire Parkway", "Bromsgrove"]`
行：2

增加路径数量将返回次短路径。有三条路径并列为第二短。

以下查询返回所有三条第二短的路径，以及两条最短路径

查询

MATCH p = SHORTEST 5 (wos:Station)-[:LINK]-+(bmv:Station)
WHERE wos.name = "Worcester Shrub Hill" AND bmv.name = "Bromsgrove"
RETURN [n in nodes(p) | n.name] AS stops

结果
经停站
`["Worcester Shrub Hill", "Droitwich Spa", "Bromsgrove"]`
`["Worcester Shrub Hill", "Worcestershire Parkway", "Bromsgrove"]`
`["Worcester Shrub Hill", "Worcester Foregate Street", "Droitwich Spa", "Bromsgrove"]`
`["Worcester Shrub Hill", "Ashchurch", "Worcestershire Parkway", "Bromsgrove"]`
`["Worcester Shrub Hill", "Ashchurch", "Cheltenham Spa", "Bromsgrove"]`
行：5

如果两个站点之间总共只有四条可能的路径，则只会返回那四条。

`ALL SHORTEST`

要返回所有并列最短长度的路径，请使用关键字 ALL SHORTEST

查询

MATCH p = ALL SHORTEST (wos:Station)-[:LINK]-+(bmv:Station)
WHERE wos.name = "Worcester Shrub Hill" AND bmv.name = "Bromsgrove"
RETURN [n in nodes(p) | n.name] AS stops

结果
经停站
`["Worcester Shrub Hill", "Droitwich Spa", "Bromsgrove"]`
`["Worcester Shrub Hill", "Worcestershire Parkway", "Bromsgrove"]`
行：2

`SHORTEST k GROUPS`

要返回并列第一、第二，一直到第 k 个最短长度的所有路径，请使用 SHORTEST k GROUPS。例如，以下查询返回 Worcester Shrub Hill 和 Bromsgrove 之间第一和第二短的长度路径

查询

MATCH p = SHORTEST 2 GROUPS (wos:Station)-[:LINK]-+(bmv:Station)
WHERE wos.name = "Worcester Shrub Hill" AND bmv.name = "Bromsgrove"
RETURN [n in nodes(p) | n.name] AS stops, length(p) AS pathLength

结果
经停站	路径长度
`["Worcester Shrub Hill", "Droitwich Spa", "Bromsgrove"]`	`2`
`["Worcester Shrub Hill", "Worcestershire Parkway", "Bromsgrove"]`	`2`
`["Worcester Shrub Hill", "Worcester Foregate Street", "Droitwich Spa", "Bromsgrove"]`	`3`
`["Worcester Shrub Hill", "Ashchurch", "Worcestershire Parkway", "Bromsgrove"]`	`3`
`["Worcester Shrub Hill", "Ashchurch", "Cheltenham Spa", "Bromsgrove"]`	`3`
行：5

第一组包含两条最短路径，其 pathLength = 2（如结果的前两行所示）；第二组包含三条第二短的路径，其 pathLength = 3（如结果的后三行所示）。

如果指定的组数多于图中实际存在的组数，则仅返回现有的路径。例如，如果为 Worcester Shrub Hill 到 Bromsgrove 指定了等于八个最短路径长度的组，则只会返回七组

查询

MATCH p = SHORTEST 8 GROUPS (wos:Station)-[:LINK]-+(bmv:Station)
WHERE wos.name = "Worcester Shrub Hill" AND bmv.name = "Bromsgrove"
RETURN length(p) AS pathLength, count(*) AS numPaths

结果
路径长度	路径数量
`2`	`2`
`3`	`3`
`4`	`1`
`5`	`4`
`6`	`8`
`7`	`10`
`8`	`6`
行：7

`ANY`

ANY 关键字可用于测试给定节点(们)的可达性。它的返回结果与 SHORTEST 1 相同，但使用 ANY 关键字可以让查询意图更清晰。例如，以下查询显示从 Pershore 到 Bromsgrove 存在一条路由，其中每对站点之间的距离小于 10 英里

查询

MATCH path = ANY
  (:Station {name: 'Pershore'})-[l:LINK WHERE l.distance < 10]-+(b:Station {name: 'Bromsgrove'})
RETURN [r IN relationships(path) | r.distance] AS distances

结果
距离
`[4.16, 3.71, 5.76, 6.16]`
行：1

分区 (Partitions)

当路径模式匹配到多个起始节点或终止节点时，匹配项会在选择最短路径之前被分区为不同的起始-终止节点对；一个分区就是一对独特的起始节点和终止节点。最短路径的选择随后会在连接给定分区内起始节点和终止节点的所有路径中进行。最后，结果由针对每个分区找到的所有最短路径的并集组成。

例如，如果匹配的起始节点被绑定到 Droitwich Spa 或 Hartlebury，终止节点被绑定到 Ashchurch 或 Cheltenham Spa，则会有四对独特的起始和终止节点，因此会有四个分区

起始节点 结束节点 (End node)

起始节点	结束节点 (End node)
`Droitwich Spa`	`Ashchurch`
`Droitwich Spa`	`Cheltenham Spa`
`Hartlebury`	`Ashchurch`
`Hartlebury`	`Cheltenham Spa`

Droitwich Spa

Ashchurch

Droitwich Spa

Cheltenham Spa

Hartlebury

Ashchurch

Hartlebury

Cheltenham Spa

以下查询说明了这些分区如何定义结果集，并在其中选择最短路径。它使用一对 UNWIND 子句来生成 Stations 名称的笛卡尔积（所有可能的起始节点和终止节点对），随后使用 MATCH 子句来查找每对独特的起始和终止 Stations 的前两组最短路径

查询

UNWIND ["Droitwich Spa", "Hartlebury"] AS a
UNWIND ["Ashchurch", "Cheltenham Spa"] AS b
MATCH SHORTEST 2 GROUPS (o:Station {name: a})-[l]-+(d:Station {name: b})
RETURN o.name AS start, d.name AS end,
    size(l) AS pathLength, count(*) AS numPaths
ORDER BY start, end, pathLength

结果
开始	结束	路径长度	路径数量
`"Droitwich Spa"`	`"Ashchurch"`	`2`	`1`
`"Droitwich Spa"`	`"Ashchurch"`	`3`	`4`
`"Droitwich Spa"`	`"Cheltenham Spa"`	`2`	`1`
`"Droitwich Spa"`	`"Cheltenham Spa"`	`3`	`1`
`"Hartlebury"`	`"Ashchurch"`	`3`	`1`
`"Hartlebury"`	`"Ashchurch"`	`4`	`4`
`"Hartlebury"`	`"Cheltenham Spa"`	`3`	`1`
`"Hartlebury"`	`"Cheltenham Spa"`	`4`	`1`
行：8

每个分区出现两次：一次用于最短路径组，一次用于次短路径组。例如，对于以 Droitwich Spa 为 start 且以 Ashchurch 为 end 的分区，最短路径组（长度为 2 的路径）有一条路径，次短路径组（长度为 3 的路径）有四条路径。

预过滤器与后过滤器

过滤器在最短路径查询中的位置将影响它是先于还是后于最短路径的选择应用。要了解差异，首先考虑一个返回从 Hartlebury 到 Cheltenham Spa 最短路径的查询

查询

MATCH SHORTEST 1
  (:Station {name: 'Hartlebury'})
  (()--(n))+
  (:Station {name: 'Cheltenham Spa'})
RETURN [stop in n[..-1] | stop.name] AS stops

结果
经停站
`["Droitwich Spa", "Bromsgrove"]`
行：1

注意，n[..-1] 是一种切片操作，返回 n 中除最后一个元素外的所有元素。如果查询改为在 MATCH 级别使用 WHERE 子句来过滤掉经由 Bromsgrove 的路由，则过滤将在选择最短路径之后应用。这将导致唯一的解决方案被移除，从而没有结果返回

查询

MATCH SHORTEST 1
  (:Station {name: 'Hartlebury'})
  (()--(n:Station))+
  (:Station {name: 'Cheltenham Spa'})
WHERE none(stop IN n[..-1] WHERE stop.name = 'Bromsgrove')
RETURN [stop in n[..-1] | stop.name] AS stops

结果
经停站
行数：0

有两种方法可以将没有解决方案的后过滤器转换为返回解决方案的预过滤器。一种是将谓词内联到路径模式中

查询

MATCH SHORTEST 1
  (:Station {name: 'Hartlebury'})
  (()--(n:Station WHERE n.name <> 'Bromsgrove'))+
  (:Station {name: 'Cheltenham Spa'})
RETURN [stop in n[..-1] | stop.name] AS stops

结果
经停站
`["Droitwich Spa", "Worcester Shrub Hill", "Ashchurch"]`
行：1

现在返回了避开 Bromsgrove 的最短行程。

另一种方法是将路径模式和过滤器用圆括号括起来（将 SHORTEST 关键字留在外面）

查询

MATCH SHORTEST 1
  ( (:Station {name: 'Hartlebury'})
    (()--(n:Station))+
    (:Station {name: 'Cheltenham Spa'})
     WHERE none(stop IN n[..-1] WHERE stop.name = 'Bromsgrove') )
RETURN [stop in n[..-1] | stop.name] AS stops

结果
经停站
`["Droitwich Spa", "Worcester Shrub Hill", "Ashchurch"]`
行：1

带有路径变量的预过滤器

上一节展示了如何通过使用圆括号在最短路径选择之前应用过滤器。然而，在最短路径关键字之前放置路径变量声明会使其位于圆括号的作用域之外。要在预过滤器中引用路径变量，必须在圆括号内进行声明。

为了说明这一点，考虑这个示例，它返回从 Hartlebury 到每个其他 Stations 的所有最短路径

查询

MATCH p = SHORTEST 1 (:Station {name: 'Hartlebury'})--+(b:Station)
RETURN b.name AS destination, length(p) AS pathLength
ORDER BY pathLength, destination

结果
目的地	路径长度
`"Droitwich Spa"`	`1`
`"Bromsgrove"`	`2`
`"Worcester Foregate Street"`	`2`
`"Worcester Shrub Hill"`	`2`
`"Ashchurch"`	`3`
`"Cheltenham Spa"`	`3`
`"Worcestershire Parkway"`	`3`
`"Pershore"`	`4`
行：8

如果修改查询以仅包含具有偶数个停靠点的路由，在 MATCH 级别添加 WHERE 子句将不起作用，因为它是一个后过滤器。它将返回之前查询的结果，并移除所有具有奇数个停靠点的路由

查询

MATCH p = SHORTEST 1 (:Station {name: 'Hartlebury'})--+(b:Station)
WHERE length(p) % 2 = 0
RETURN b.name AS destination, length(p) AS pathLength
ORDER BY pathLength, destination

结果
目的地	路径长度
`"Bromsgrove"`	`2`
`"Worcester Foregate Street"`	`2`
`"Worcester Shrub Hill"`	`2`
`"Pershore"`	`4`
行：4

要将谓词移动到预过滤器，应在圆括号内引用路径变量，然后将为所有目的地返回具有偶数个停靠点的最短路由

查询

MATCH SHORTEST 1
  (p = (:Station {name: 'Hartlebury'})--+(b:Station)
    WHERE length(p) % 2 = 0 )
RETURN b.name AS destination, length(p) AS pathLength
ORDER BY pathLength, destination

结果
目的地	路径长度
`"Bromsgrove"`	`2`
`"Worcester Foregate Street"`	`2`
`"Worcester Shrub Hill"`	`2`
`"Ashchurch"`	`4`
`"Cheltenham Spa"`	`4`
`"Droitwich Spa"`	`4`
`"Pershore"`	`4`
`"Worcestershire Parkway"`	`4`
行：8

性能与规划

当 Cypher 规划器能够识别最短路径的单个源-目标节点对时，最短路径查询通常执行得更好。这是因为规划器可以使用从源节点和目标节点出发的双向搜索，并在找到它们之间的最短路径时终止，而不是为了寻找潜在的目标节点而遍历整个图。然而，虽然有一些策略可以强制执行这种优化，但强制 Cypher 使用它们并不总是能提高性能。

如果规划器评估出一个单一的源-目标节点对，Cypher 会使用 ShortestPath 或 StatefulShortestPath(Into) 运算符；否则，它会使用 StatefulShortestPath(All)。每个运算符及其使用标准概述如下。

对于不熟悉 Cypher 执行计划和运算符的读者，建议先阅读理解执行计划。

示例图

本节使用一个结构为树状的图，分支因子为三，深度为九。这意味着图以一个根节点开始，每个节点产生三个子节点，这种模式持续九层。总共包含近 90,000 个节点。

每个节点 (N) 都有一个 trail 属性，用作“面包屑”列表，追踪从树根到该节点的路径（根节点的 trail 属性为空列表）。该轨迹记录了到达每个节点所采取的 "A"、"B" 或 "C" 的选择，构建了一个随每层级增加而变长的序列。这确保了图中的每个 trail 值都是唯一的。

要重新创建该图，请在空的 Neo4j 数据库中运行以下查询

WITH 9 AS depth, 3 AS branching
CREATE (:N {level: 0, trail: []})
WITH *
UNWIND range(0, depth) AS level
CALL (branching, level) {
   MATCH (n {level: level})
   UNWIND ["A", "B", "C"] AS branch
   CREATE (n)-[:R]->(:N {level: level + 1, trail: n.trail + [branch]})
};
CREATE RANGE INDEX level_index FOR (n:N) ON n.level

使用 `CALL` 子查询强制执行单一源-目标节点对

Cypher 强制执行最短路径单一源-目标对的一种方法是重写查询以包含 CALL 子查询。这是因为使用 CALL 时，每个传入的行都已经绑定了源节点和目标节点，因此每个节点的基数（即计数）已知为 1。如果没有 CALL，规划器不知道每个源节点有多少个目标，即使它仍然为每个源运行一次最短路径搜索，这也可能生成效率较低的查询。

示例 1. CALL 子查询与最短路径查询性能

查找两个节点之间的最短路径

PROFILE
MATCH p = ANY SHORTEST
  (source:N {trail: ["C", "C", "A", "C", "A", "B", "B", "B", "A"]})--{2,}
  (target:N {trail: ["A", "B", "C", "A", "B", "C", "A", "B", "C"]})
RETURN length(p) AS pathLength

结果
路径长度
`18`
行：1

此查询生成的计划显示，即使 trail 属性在图中对于每个节点都是唯一的（尚未在此属性上创建索引），规划器也无法确定单一源-目标节点对的存在。因此，它必须耗尽所有可能的目标节点，才能使用 StatefulShortestPath(All) 运算符确定从源出发的最短路径。

查询计划

+-----------------------------------+----+-------------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------------+
| Operator                          | Id | Details                                                                 | Estimated Rows | Rows  | DB Hits | Memory (Bytes) | Page Cache Hits/Misses | Time (ms) | Pipeline            |
+-----------------------------------+----+-------------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------------+
| +ProduceResults                   |  0 | pathLength                                                              |       19612941 |     1 |       0 |              0 |                    0/0 |     0.088 |                     |
| |                                 +----+-------------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+                     |
| +Projection                       |  1 | length((source)-[anon_39*]-(target)) AS pathLength                      |       19612941 |     1 |      17 |                |                    9/0 |     0.091 |                     |
| |                                 +----+-------------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+                     |
| +StatefulShortestPath(All, Trail) |  2 | SHORTEST 1 (source) ((`anon_35`)-[`anon_36`]-(`anon_37`)){2, } (target) |       19612941 |     1 |  354300 |       65608284 |                85662/0 |   158.664 | In Pipeline 1       |
| |                                 |    |         expanding from: source                                          |                |       |         |                |                        |           |                     |
| |                                 |    |     inlined predicates: target.trail = $autolist_1                      |                |       |         |                |                        |           |                     |
| |                                 |    |                         target:N                                        |                |       |         |                |                        |           |                     |
| |                                 +----+-------------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------------+
| +Filter                           |  3 | source.trail = $autolist_0                                              |           4429 |     1 |  177146 |                |                        |           |                     |
| |                                 +----+-------------------------------------------------------------------------+----------------+-------+---------+----------------+                        |           |                     |
| +NodeByLabelScan                  |  4 | source:N                                                                |          88573 | 88573 |   88574 |            376 |                 1853/0 |    53.311 | Fused in Pipeline 0 |
+-----------------------------------+----+-------------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------------+

Total database accesses: 620037, total allocated memory: 65608620

1 row
ready to start consuming query after 45 ms, results consumed after another 214 ms

然而，由于每个 trail 属性都是唯一的，重写查询以使用 CALL 子查询会产生更高效的计划。这是因为它强制规划器使用 StatefulShortestPath(Into) 运算符，该运算符从源节点扩展直到找到其特定的目标节点，并确保 ANY SHORTEST 对每个源-目标对执行一次。

用 CALL 子查询重写的最短路径查询

PROFILE
MATCH (start:N {trail: ["C", "C", "A", "C", "A", "B", "B", "B", "A"]}),
      (end:N {trail: ["A", "B", "C", "A", "B", "C", "A", "B", "C"]})
CALL (start, end) {
   MATCH p = ANY SHORTEST (start)--{2,}(end)
   RETURN p
}
RETURN length(p) AS pathLength

结果是查询速度显著加快（从 45 毫秒下降到 4 毫秒）

查询计划

+------------------------------------+----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------------+
| Operator                           | Id | Details                                                             | Estimated Rows | Rows  | DB Hits | Memory (Bytes) | Page Cache Hits/Misses | Time (ms) | Pipeline            |
+------------------------------------+----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------------+
| +ProduceResults                    |  0 | pathLength                                                          |       19612941 |     1 |       0 |              0 |                    0/0 |     0.080 |                     |
| |                                  +----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+                     |
| +Projection                        |  1 | length(p) AS pathLength                                             |       19612941 |     1 |       0 |                |                    0/0 |     0.023 |                     |
| |                                  +----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+                     |
| +Projection                        |  2 | (start)-[anon_15*]-(end) AS p                                       |       19612941 |     1 |      17 |                |                    9/0 |     0.063 |                     |
| |                                  +----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+                     |
| +StatefulShortestPath(Into, Trail) |  3 | SHORTEST 1 (start) ((`anon_11`)-[`anon_12`]-(`anon_13`)){2, } (end) |       19612941 |     1 |    1952 |        1337576 |                  209/0 |     1.938 | In Pipeline 3       |
| |                                  +----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------------+
| +CartesianProduct                  |  4 |                                                                     |       19612941 |     1 |       0 |           9040 |                        |     0.054 | In Pipeline 2       |
| |\                                 +----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------------+
| | +Filter                          |  5 | end.trail = $autolist_1                                             |          22143 |     1 |  177146 |                |                        |           |                     |
| | |                                +----+---------------------------------------------------------------------+----------------+-------+---------+----------------+                        |           |                     |
| | +NodeByLabelScan                 |  6 | end:N                                                               |         442865 | 88573 |   88574 |            392 |                 1853/0 |    44.047 | Fused in Pipeline 1 |
| |                                  +----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------------+
| +Filter                            |  7 | start.trail = $autolist_0                                           |           4429 |     1 |  177146 |                |                        |           |                     |
| |                                  +----+---------------------------------------------------------------------+----------------+-------+---------+----------------+                        |           |                     |
| +NodeByLabelScan                   |  8 | start:N                                                             |          88573 | 88573 |   88574 |            376 |                 1853/0 |    57.818 | Fused in Pipeline 0 |
+------------------------------------+----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------------+

Total database accesses: 533409, total allocated memory: 1346888

1 row
ready to start consuming query after 4 ms, results consumed after another 106 ms

使用索引和约束强制执行单一源-目标节点对

向规划器告知最短路径中目标节点唯一性的另一种方法是在最短路径中的匹配节点所属的属性上创建索引或属性唯一性/键约束（两者均由索引支持）。这将准确告知规划器节点基数，从而实现更高效的查询规划（假设图中包含唯一标识节点的属性）。

示例 2. 索引和约束的影响

在 trail 属性上创建属性唯一性约束

CREATE CONSTRAINT unique_trail FOR (n:N) REQUIRE n.trail IS UNIQUE

此约束将预先告知规划器 trail 值的唯一性。因此，更简单的最短路径查询（没有 CALL 子查询）现在将生成更快的计划（使用 StatefulShortestPath(Into) 运算符），最短路径的源节点和目标节点的基数均为 1。

查找两个节点之间的最短路径

PROFILE
MATCH p = ANY SHORTEST
  (source:N {trail: ["C", "C", "A", "C", "A", "B", "B", "B", "A"]})--{2,}
  (target:N {trail: ["A", "B", "C", "A", "B", "C", "A", "B", "C"]})
RETURN length(p) AS pathLength

查询计划

+------------------------------------+----+----------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+
| Operator                           | Id | Details                                                                                            | Estimated Rows | Rows | DB Hits | Memory (Bytes) | Page Cache Hits/Misses | Time (ms) | Pipeline      |
+------------------------------------+----+----------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+
| +ProduceResults                    |  0 | pathLength                                                                                         |              1 |    1 |       0 |              0 |                    0/0 |     0.058 |               |
| |                                  +----+----------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+               |
| +Projection                        |  1 | length((source)-[anon_55*]-(target)) AS pathLength                                                 |              1 |    1 |      17 |                |                    9/0 |     0.081 |               |
| |                                  +----+----------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+               |
| +StatefulShortestPath(Into, Trail) |  2 | SHORTEST 1 (source) ((`anon_51`)-[`anon_52`]-(`anon_53`)){2, } (target)                            |              1 |    1 |    1952 |        1337568 |                  209/0 |     2.213 | In Pipeline 1 |
| |                                  +----+----------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+
| +MultiNodeIndexSeek                |  3 | UNIQUE source:N(trail) WHERE trail = $autolist_0, UNIQUE target:N(trail) WHERE trail = $autolist_1 |              1 |    1 |       4 |            376 |                    1/5 |     0.400 | In Pipeline 0 |
+------------------------------------+----+----------------------------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------+

Total database accesses: 1957, total allocated memory: 990608

1 row
ready to start consuming query after 48 ms, results consumed after another 3 ms

强制执行单一源-目标节点对的局限性

强制执行单一源-目标节点对并不总是可取的。对于一个源和多个目标，使用 CALL 子查询重写最短路径查询会强制规划器使用 ShortestPath 或 StatefulShortestPath(Into) 运算符，这些运算符每个目标节点运行一次。虽然这对单个对很有效，但随着目标数量的增加，它可能会变慢，因为它强制规划器为每一对源-目标节点遍历图。在这种情况下，让规划器使用 StatefulShortestPath(All) 可能更有效，它在整个图中扩展一次并返回所有匹配项。

示例 3. 多目标最短路径的高效规划

考虑以下查询，它没有指定唯一的目标节点，并从源节点生成了总共 19682 条最短路径

查找通往多个目标节点的最短路径

PROFILE
MATCH p = ANY SHORTEST
  (start:N {trail: ["C", "C", "A", "C", "A", "B", "B", "B", "A"]})--{2,}
  (end:N {level: 9})
RETURN count(*) AS pathCount

结果
路径长度
`19682`
行：1

由于存在多个目标节点而没有指定唯一的属性值（图中 level 属性值为 9 的节点有 19683 个），规划器将默认使用 StatefulShortestPath(All) 运算符，该运算符从源节点扩展一次，直到找到所有有效最短路径。

查询计划

+-----------------------------------+----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------+
| Operator                          | Id | Details                                                             | Estimated Rows | Rows  | DB Hits | Memory (Bytes) | Page Cache Hits/Misses | Time (ms) | Pipeline      |
+-----------------------------------+----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------+
| +ProduceResults                   |  0 | pathCount                                                           |              1 |     1 |       0 |              0 |                    0/0 |     0.082 |               |
| |                                 +----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+               |
| +EagerAggregation                 |  1 | count(*) AS pathCount                                               |              1 |     1 |       0 |             40 |                    0/0 |     1.151 | In Pipeline 2 |
| |                                 +----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------+
| +StatefulShortestPath(All, Trail) |  2 | SHORTEST 1 (start) ((`anon_19`)-[`anon_20`]-(`anon_21`)){2, } (end) |           8052 | 19682 |  373982 |       82162292 |                65705/0 |   455.921 | In Pipeline 1 |
| |                                 |    |         expanding from: start                                       |                |       |         |                |                        |           |               |
| |                                 |    |     inlined predicates: end.level = $autoint_1                      |                |       |         |                |                        |           |               |
| |                                 |    |                         end:N                                       |                |       |         |                |                        |           |               |
| |                                 +----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------+
| +NodeUniqueIndexSeek              |  3 | UNIQUE start:N(trail) WHERE trail = $autolist_0                     |              1 |     1 |       2 |            376 |                    3/0 |     0.509 | In Pipeline 0 |
+-----------------------------------+----+---------------------------------------------------------------------+----------------+-------+---------+----------------+------------------------+-----------+---------------+

Total database accesses: 373984, total allocated memory: 82162652

1 row
ready to start consuming query after 83 ms, results consumed after another 592 ms

如果用 CALL 子查询重写查询，规划器将使用 StatefulShortestPath(Into) 运算符，它对每一对源-目标节点执行单独的遍历。

用 CALL 子查询重写的多目标最短路径查询

PROFILE
MATCH (start:N {trail: ["C", "C", "A", "C", "A", "B", "B", "B", "A"]}),
      (end:N {level: 9})
CALL (start, end) {
   MATCH p = ANY SHORTEST (start)--{2,}(end)
   RETURN p
}
RETURN count(*) AS pathCount

查询计划

+------------------------------------+----+----------------------------------------------------------------------------------------------------+----------------+-------+----------+----------------+------------------------+-----------+---------------+
| Operator                           | Id | Details                                                                                            | Estimated Rows | Rows  | DB Hits  | Memory (Bytes) | Page Cache Hits/Misses | Time (ms) | Pipeline      |
+------------------------------------+----+----------------------------------------------------------------------------------------------------+----------------+-------+----------+----------------+------------------------+-----------+---------------+
| +ProduceResults                    |  0 | pathCount                                                                                          |              1 |     1 |        0 |              0 |                    0/0 |     0.185 |               |
| |                                  +----+----------------------------------------------------------------------------------------------------+----------------+-------+----------+----------------+------------------------+-----------+               |
| +EagerAggregation                  |  1 | count(*) AS pathCount                                                                              |              1 |     1 |        0 |             40 |                    0/0 |     1.571 | In Pipeline 2 |
| |                                  +----+----------------------------------------------------------------------------------------------------+----------------+-------+----------+----------------+------------------------+-----------+---------------+
| +Projection                        |  2 | (start)-[anon_15*]-(end) AS p                                                                      |           8052 | 19682 |   314930 |                |               189543/0 |    67.007 |               |
| |                                  +----+----------------------------------------------------------------------------------------------------+----------------+-------+----------+----------------+------------------------+-----------+               |
| +StatefulShortestPath(Into, Trail) |  3 | SHORTEST 1 (start) ((`anon_11`)-[`anon_12`]-(`anon_13`)){2, } (end)                                |           8052 | 19682 | 32986690 |      221424672 |              3775866/0 | 22680.410 | In Pipeline 1 |
| |                                  +----+----------------------------------------------------------------------------------------------------+----------------+-------+----------+----------------+------------------------+-----------+---------------+
| +MultiNodeIndexSeek                |  4 | UNIQUE start:N(trail) WHERE trail = $autolist_0, RANGE INDEX end:N(level) WHERE level = $autoint_1 |           8052 | 19683 |    19686 |            376 |                   57/0 |    12.979 | In Pipeline 0 |
+------------------------------------+----+----------------------------------------------------------------------------------------------------+----------------+-------+----------+----------------+------------------------+-----------+---------------+

Total database accesses: 33321306, total allocated memory: 221425168

1 row
ready to start consuming query after 49 ms, results consumed after another 22774 ms

正如计划所示，在这种情况下，强制执行单一源-目标节点对并不更高效。相反，这样做确保了 StatefulShortestPath(Into) 运算符被执行 19682 次，即每一对源-目标节点一次，从而生成了更昂贵的查询。

最短路径运算符

Cypher 使用三种不同的运算符来规划最短路径查询。下表概述了使用每种运算符的标准。

运算符描述标准

运算符	描述	标准
`ShortestPath`	从目标和源节点执行双向广度优先搜索 (BFS)。当找到它们之间的最短路径时终止。	使用场景当使用 `shortestPath()` 或 `allShortestPaths()` 函数时。或者，当最短路径中源和目标节点的预估基数为 1 或更少，且以下各项均为真时选择器为以下之一：`SHORTEST 1`、`ANY`、`ANY SHORTEST`、`ALL SHORTEST`、`SHORTEST GROUP` 或 `SHORTEST 1 GROUP`。只有一个关系模式。如果模式是 `(()-[]-())` 形式的量化路径模式，或量化关系，并且它使用了可以直接应用于关系的过滤器。如果模式是量化路径模式或量化关系，且量词的下界为 0 或 1。对于量化路径模式，量化路径模式内部没有声明在其他地方引用的节点变量。
`StatefulShortestPath(Into)`	从目标和源节点执行双向 BFS。当找到它们之间的最短路径时终止。	当最短路径中源和目标节点的预估基数为 1 或更少，且以下任一条件为真时使用选择器为以下之一：`ANY/SHORTEST k` 或 `SHORTEST k GROUPS`，且 `k` 大于 `1`。存在多个关系模式。
`StatefulShortestPath(All)`	执行单向 BFS 以查找从源节点到所有匹配目标节点条件的节点的最短路径。	当规划器在最短路径中估计出多于一个源-目标节点对时使用。

ShortestPath

从目标和源节点执行双向广度优先搜索 (BFS)。当找到它们之间的最短路径时终止。

使用场景

当使用 shortestPath() 或 allShortestPaths() 函数时。

或者，当最短路径中源和目标节点的预估基数为 1 或更少，且以下各项均为真时

选择器为以下之一：SHORTEST 1、ANY、ANY SHORTEST、ALL SHORTEST、SHORTEST GROUP 或 SHORTEST 1 GROUP。
只有一个关系模式。
如果模式是 (()-[]-()) 形式的量化路径模式，或量化关系，并且它使用了可以直接应用于关系的过滤器。
如果模式是量化路径模式或量化关系，且量词的下界为 0 或 1。
对于量化路径模式，量化路径模式内部没有声明在其他地方引用的节点变量。

StatefulShortestPath(Into)

从目标和源节点执行双向 BFS。当找到它们之间的最短路径时终止。

当最短路径中源和目标节点的预估基数为 1 或更少，且以下任一条件为真时使用

选择器为以下之一：ANY/SHORTEST k 或 SHORTEST k GROUPS，且 k 大于 1。
存在多个关系模式。

StatefulShortestPath(All)

执行单向 BFS 以查找从源节点到所有匹配目标节点条件的节点的最短路径。

当规划器在最短路径中估计出多于一个源-目标节点对时使用。

StatefulShortestPath(Into) 和 StatefulShortestPath(All) 可以匹配比 ShortestPath 更复杂的最短路径。因此，使用这些运算符的查询可能会更慢且成本更高。

`ShortestPath` 运算符：快速搜索 vs. 穷举搜索

使用 ShortestPath 运算符规划的查询（参见上表中关于何时使用此运算符的说明），根据查询中的谓词使用两种不同的搜索算法。

如果谓词可以在搜索过程中进行检查（例如，要求路径中的每条关系都具有特定属性），则规划器可以提前排除无效路径。在这种情况下，使用快速双向广度优先搜索 (BFS) 算法。

快速搜索算法

MATCH (start:N {level: 1}), (end:N {level: 5})
MATCH p = shortestPath((start)-[r*]-(end))
WHERE all(rel IN r WHERE rel.flag IS NULL)
RETURN p

如果谓词要求在路径匹配后检查整个路径（例如检查路径长度是否超过某个值），规划器就无法提前排除路径。在这种情况下，使用较慢的穷举搜索算法。在某些情况下，穷举搜索可能会非常耗时，例如当两个节点之间不存在最短路径时（为禁止穷举搜索，请将 dbms.cypher.forbid_exhaustive_shortestpath 设置为 true）。

穷举搜索算法

MATCH (start:N {level: 1}), (end:N {level: 5})
MATCH p = shortestPath((start)-[*]-(end))
WHERE length(p) > 3
RETURN p

对于本应触发穷举搜索的查询，一种实用的解决方法是先绑定匹配的路径，然后使用 FILTER 子句对其进行过滤（FILTER 是一个单独的子句，执行匹配后的过滤，这与 WHERE 不同，后者为 MATCH 子句匹配的模式增加约束）。这允许规划器在查找最短路径时使用快速搜索算法，并在之后才应用过滤器。请注意，因为过滤器是在快速算法运行后应用的，所以它可能会消除所有候选路径并返回空结果。

重写为使用快速搜索算法的查询

MATCH (start:N {level: 1}), (end:N {level: 5})
MATCH p = shortestPath((start)-[*]-(end))
FILTER length(p) > 3
RETURN p

最短路径

关于 Cypher 和 GDS 最短路径的说明

SHORTEST k

ALL SHORTEST

SHORTEST k GROUPS

ANY

分区 (Partitions)

预过滤器与后过滤器

带有路径变量的预过滤器

性能与规划

示例图

使用 CALL 子查询强制执行单一源-目标节点对

使用索引和约束强制执行单一源-目标节点对

强制执行单一源-目标节点对的局限性

最短路径运算符

ShortestPath 运算符：快速搜索 vs. 穷举搜索

`SHORTEST k`

`ALL SHORTEST`

`SHORTEST k GROUPS`

`ANY`

使用 `CALL` 子查询强制执行单一源-目标节点对

`ShortestPath` 运算符：快速搜索 vs. 穷举搜索