最短路径

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"]`
`["伍斯特灌木丛山", "阿什丘奇", "切尔滕纳姆温泉", "布罗姆斯格罗夫"]`
行数：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。例如，以下代码返回伍斯特灌木丛山和布罗姆斯格罗夫之间第一短和第二短的路径

查询

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`
`["伍斯特灌木丛山", "阿什丘奇", "切尔滕纳姆温泉", "布罗姆斯格罗夫"]`	`3`
行数：5

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

如果指定的组数超过图中存在的组数，则只返回存在的路径。例如，如果为伍斯特灌木丛山到布罗姆斯格罗夫指定了等于八条最短路径之一的路径，则只会返回七组

查询

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关键字可以使查询的意图更清晰。例如，以下查询显示存在从珀肖尔到布罗姆斯格罗夫的路线，其中每个车站对之间的距离小于 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. 结果
distances
`[4.16, 3.71, 5.76, 6.16]`
行数：1

分区

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

例如，如果匹配项的起点节点绑定到德罗伊奇温泉或哈特勒伯里，而终点节点绑定到阿什丘奇或切尔滕纳姆温泉，则将存在四个不同的起点和终点节点对，因此存在四个分区

起点节点 终点节点

起点节点	终点节点
`德罗伊奇温泉`	`阿什丘奇`
`德罗伊奇温泉`	`切尔滕纳姆温泉`
`哈特勒伯里`	`阿什丘奇`
`哈特勒伯里`	`切尔滕纳姆温泉`

德罗伊奇温泉

阿什丘奇

德罗伊奇温泉

切尔滕纳姆温泉

哈特勒伯里

阿什丘奇

哈特勒伯里

切尔滕纳姆温泉

以下查询说明了这些分区如何定义选择最短路径的结果集。它使用一对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. 结果
start	end	pathLength	numPaths
`"德罗伊奇温泉"`	`"阿什丘奇"`	`2`	`1`
`"德罗伊奇温泉"`	`"阿什丘奇"`	`3`	`4`
`"德罗伊奇温泉"`	`"切尔滕纳姆温泉"`	`2`	`1`
`"德罗伊奇温泉"`	`"切尔滕纳姆温泉"`	`3`	`1`
`"哈特勒伯里"`	`"阿什丘奇"`	`3`	`1`
`"哈特勒伯里"`	`"阿什丘奇"`	`4`	`4`
`"哈特勒伯里"`	`"切尔滕纳姆温泉"`	`3`	`1`
`"哈特勒伯里"`	`"切尔滕纳姆温泉"`	`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. 结果
站点
`["德罗伊奇温泉", "布罗姆斯格罗夫"]`
行数：1

请注意，n[..-1]是一个切片操作，它返回n的所有元素，除了最后一个。如果查询改为在MATCH级别使用WHERE子句过滤掉经过布罗姆斯格罗夫的路线，则过滤将在选择最短路径后应用。这会导致唯一解决方案被移除，并且不返回任何结果

查询

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. 结果
站点
`["德罗伊奇温泉", "伍斯特灌木丛山", "阿什丘奇"]`
行数：1

现在返回了避免布罗姆斯格罗夫的最短行程。

另一种方法是用括号括起路径模式和过滤器（将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. 结果
站点
`["德罗伊奇温泉", "伍斯特灌木丛山", "阿什丘奇"]`
行数：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. 结果
destination	pathLength
`"德罗伊奇温泉"`	`1`
`"布罗姆斯格罗夫"`	`2`
`"伍斯特福盖特街"`	`2`
`"伍斯特灌木丛山"`	`2`
`"阿什丘奇"`	`3`
`"切尔滕纳姆温泉"`	`3`
`"伍斯特郡公园"`	`3`
`"珀肖尔"`	`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. 结果
destination	pathLength
`"布罗姆斯格罗夫"`	`2`
`"伍斯特福盖特街"`	`2`
`"伍斯特灌木丛山"`	`2`
`"珀肖尔"`	`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. 结果
destination	pathLength
`"布罗姆斯格罗夫"`	`2`
`"伍斯特福盖特街"`	`2`
`"伍斯特灌木丛山"`	`2`
`"阿什丘奇"`	`4`
`"切尔滕纳姆温泉"`	`4`
`"德罗伊奇温泉"`	`4`
`"珀肖尔"`	`4`
`"伍斯特郡公园"`	`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 |
+-----------------------------+----+----------------------------------------------------------------------------------+----------------+------+---------+----------------+------------------------+-----------+---------------------+

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