最短路径

Cypher^® 关键字 SHORTEST 用于查找节点之间最短路径的变体。这包括查找最短路径、次短路径（以此类推）、所有可用的最短路径以及包含相同模式长度的路径组的能力。ANY 关键字可用于测试从给定节点（或多个节点）的可达性，本文也将对此进行解释，以及如何在查询中使用 SHORTEST 应用过滤器。

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

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

Cypher 和 Neo4j 的图数据科学 (GDS) 库都可用于查找节点之间最短路径的变体。

在以下情况下使用 Cypher：

你需要通过量化路径模式指定复杂的图导航。
创建图投影耗时过长。
你的实例中没有 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 是要匹配的路径数量。例如，以下示例使用 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 关系上双向行驶。+ 量词表示应匹配一个或多个关系。有关更多信息，请参阅语法和语义 - 量化关系。

表 1. 结果
结果
`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

表 2. 结果
站点
`["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

表 3. 结果
站点
`["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

表 4. 结果
站点
`["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

表 5. 结果
站点	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

表 6. 结果
pathLength	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

表 7. 结果
距离
`[4.16, 3.71, 5.76, 6.16]`
行数：1

分区

当有多个起始节点或结束节点匹配路径模式时，匹配项将在选择最短路径之前被分区为不同的起始节点和结束节点对；一个分区是一个不同的起始节点和结束节点对。然后，从连接给定分区的起始节点和结束节点的所有路径中选择最短路径。结果由为每个分区找到的所有最短路径的并集组成。

例如，如果匹配的起始节点绑定到 Droitwich Spa 或 Hartlebury，并且结束节点绑定到 Ashchurch 或 Cheltenham Spa，则将有四对不同的起始节点和结束节点，因此有四个分区：

起始节点 结束节点

起始节点	结束节点
`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

表 8. 结果
起始	结束	pathLength	numPaths
`"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

表 9. 结果
站点
`["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

表 10. 结果
站点
行数：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

表 11. 结果
站点
`["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

表 12. 结果
站点
`["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

表 13. 结果
目的地	pathLength
`"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

表 14. 结果
目的地	pathLength
`"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

表 15. 结果
目的地	pathLength
`"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 执行计划和运算符的读者，建议首先阅读理解执行计划一节。

规划 SHORTEST 查询时使用两个运算符：

StatefulShortestPath(All) - 使用单向广度优先搜索算法查找从先前匹配的起始节点到尚未匹配的结束节点的最短路径。
StatefulShortestPath(Into) - 使用双向广度优先搜索 (BFS) 算法，其中同时执行两个 BFS 调用，一个从左边界节点开始，一个从右边界节点开始。

当最短路径中的两个边界节点都估计最多匹配一个节点时，规划器使用 StatefulShortestPath(Into)。否则，使用 StatefulShortestPath(All)。

例如，规划器估计以下查询中的左边界节点将匹配一个节点，右边界节点将匹配五个节点，并选择从左边界节点扩展。使用 StatefulShortestPath(Into) 将需要五次双向广度优先搜索 (BFS) 调用，而 StatefulShortestPath(All) 将只需要一次单向 BFS 调用。因此，该查询将使用 StatefulShortestPath(All)。

使用 StatefulShortestPath(All) 规划的查询

PROFILE
MATCH
  p = SHORTEST 1 (a:Station {name: "Worcestershire Parkway"})(()-[]-()-[]-()){1,}(b:Station)
RETURN p

结果

+----------------------------+----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| Operator                   | Id | Details                                                                          | Estimated Rows | Rows | DB Hits | Memory (Bytes) | Page Cache Hits/Misses | Time (ms) | Pipeline            |
+----------------------------+----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| +ProduceResults            |  0 | p                                                                                |              5 |    9 |     122 |              0 |                    0/0 |    10.967 |                     |
| |                          +----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+                     |
| +Projection                |  1 | (a) ((anon_12)-[anon_14]-(anon_13)-[anon_11]-())* (b) AS p                       |              5 |    9 |       0 |                |                    0/0 |     0.063 |                     |
| |                          +----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+                     |
| +StatefulShortestPath(All) |  2 | SHORTEST 1 (a) ((`anon_5`)-[`anon_6`]-(`anon_7`)-[`anon_8`]-(`anon_9`)){1, } (b) |              5 |    9 |      80 |          18927 |                    0/0 |     1.071 | In Pipeline 1       |
| |                          |    |         expanding from: a                                                        |                |      |         |                |                        |           |                     |
| |                          |    |     inlined predicates: b:Station                                                |                |      |         |                |                        |           |                     |
| |                          +----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| +Filter                    |  3 | a.name = $autostring_0                                                           |              1 |    1 |      18 |                |                        |           |                     |
| |                          +----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+                        |           |                     |
| +NodeByLabelScan           |  4 | a:Station                                                                        |             10 |    9 |      10 |            376 |                    3/0 |     0.811 | Fused in Pipeline 0 |
+----------------------------+----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+

然而，偏好 StatefulShortestPath(All) 的启发式方法可能会导致查询性能变差。为了让规划器选择 StatefulShortestPath(Into)，请使用CALL 子查询重写查询，该子查询将为每个传入行执行一次。

例如，在以下查询中，使用 CALL 子查询可确保规划器为每个执行行将 a 和 b 分别绑定到恰好一个 Station 节点，这会强制它为 CALL 子查询的每次调用使用 StatefulShortestPath(Into)，因为使用此运算符的前提条件是两个边界节点都恰好匹配一个节点。

以下查询使用变量作用域子句（在 Neo4j 5.23 中引入）将变量导入到 CALL 子查询中。如果您使用的是旧版本的 Neo4j，请改用导入 WITH 子句。

重写为使用 StatefulShortestPath(Into) 的查询

PROFILE
MATCH
  (a:Station {name: "Worcestershire Parkway"}),
  (b:Station)
CALL (a, b) {
  MATCH
    p = SHORTEST 1 (a)(()-[]-()-[]-()){1,}(b)
  RETURN p
}
RETURN p

结果

+-----------------------------+----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| Operator                    | Id | Details                                                                          | Estimated Rows | Rows | DB Hits | Memory (Bytes) | Page Cache Hits/Misses | Time (ms) | Pipeline            |
+-----------------------------+----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| +ProduceResults             |  0 | p                                                                                |              5 |    9 |     122 |              0 |                    0/0 |     0.561 |                     |
| |                           +----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+                     |
| +Projection                 |  1 | (a) ((anon_12)-[anon_14]-(anon_13)-[anon_11]-())* (b) AS p                       |              5 |    9 |       0 |                |                    0/0 |     0.060 |                     |
| |                           +----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+                     |
| +StatefulShortestPath(Into) |  2 | SHORTEST 1 (a) ((`anon_5`)-[`anon_6`]-(`anon_7`)-[`anon_8`]-(`anon_9`)){1, } (b) |              5 |    9 |     176 |          17873 |                    0/0 |     2.273 | In Pipeline 3       |
| |                           +----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| +CartesianProduct           |  3 |                                                                                  |              5 |    9 |       0 |           2056 |                    0/0 |     0.048 | In Pipeline 2       |
| |\                          +----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| | +NodeByLabelScan          |  4 | b:Station                                                                        |             10 |    9 |      10 |            392 |                    1/0 |     0.023 | In Pipeline 1       |
| |                           +----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+
| +Filter                     |  5 | a.name = $autostring_0                                                           |              1 |    1 |      18 |                |                        |           |                     |
| |                           +----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+                        |           |                     |
| +NodeByLabelScan            |  6 | a:Station                                                                        |             10 |    9 |      10 |            376 |                    3/0 |     0.089 | Fused in Pipeline 0 |
+-----------------------------+----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+

有时，规划器无法对模式节点将匹配多少节点做出可靠的估计。考虑在适用的情况下使用属性唯一性约束来帮助规划器获得更可靠的估计。