概述
两点间的最短路径是边数最少的路径。使用以下路径选择前缀可从匹配结果的每个分区选择最短路径。
路径选择 |
描述 |
|---|---|
ALL SHORTEST |
从每个分区选择所有最短路径 |
ANY SHORTEST |
从每个分区选择任意一条最短路径 |
SHORTEST k |
从每个分区选择任意k（非负整数）条最短路径；若一个分区的最短路径数量少于k，则继续选择次短路径、第三最短路径，以此类推，直到满足数量或无更多路径可选 |
SHORTEST k GROUP |
在每个分区中，根据长度对路径进行分组并按升序排列，再选择前k组的所有路径 |
最短路径选择一般与变长的带量词路径一起使用。当使用最短路径选择时，路径约束强制使用TRAIL，即路径中不允许出现重复边。
关于最短路径算法
嬴图算法库提供以下最短路径算法：
这些算法适用于计算加权最短路径（即开销最低的路径），或基于加载至HDC服务器的全图或子图计算最短路径。
示例图
CREATE GRAPH myGraph {
NODE City ({name string}),
EDGE Links ()-[]->()
} PARTITION BY HASH(Crc32) SHARDS [1]
INSERT (zenith:City {_id: "Zenith"}),
(arcadia:City {_id: "Arcadia"}),
(verona:City {_id: "Verona"}),
(nebula:City {_id: "Nebula"}),
(mirage:City {_id: "Mirage"}),
(lunaria:City {_id: "Lunaria"}),
(solara:City {_id: "Solara"}),
(eldoria:City {_id: "Eldoria"}),
(nexis:City {_id: "Nexis"}),
(arcadia)-[:Links]->(zenith),
(arcadia)-[:Links]->(verona),
(arcadia)-[:Links]->(solara),
(mirage)-[:Links]->(arcadia),
(nebula)-[:Links]->(verona),
(mirage)-[:Links]->(nebula),
(verona)-[:Links]->(mirage),
(mirage)-[:Links]->(eldoria),
(solara)-[:Links]->(eldoria),
(lunaria)-[:Links]->(solara)
ALL SHORTEST
MATCH p = ALL SHORTEST (a)-[:Links]-{1,10}(b)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p
结果：p
ANY SHORTEST
MATCH p = ANY SHORTEST (a)-[:Links]-{1,10}(b)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p
结果：p
SHORTEST k
MATCH p = SHORTEST 2 (a)-[:Links]-{1,10}(b)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p
结果：p
MATCH p = SHORTEST 3 (a)-[:Links]-{1,10}(b)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p
由于Arcadia和Eldoria之间只有两条长度为2的最短路径，因此需要再选择一条次短路径。本例中次短路径长度为3，且只有1条，因此返回以下三条路径：
SHORTEST k GROUP
MATCH p = SHORTEST 3 GROUP (a)-[:Links]-{1,10}(b)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p
查询返回两条长度为2的最短路径，一条长度为3的次短路径，以及一条长度为4的第三短路径：
分区
当匹配的路径包含多个起点和终点时，系统会根据不同的起、终点对将结果进行概念上的分区。最短路径的选择在每个分区中分别进行，最终的结果是从所有分区选择的最短路径的并集。
本查询中，首先对a和b进行笛卡尔乘积，随后在路径模板中被引用，因此共有四条最短路径从四个分区中被选择：
MATCH p = SHORTEST 1 (a)-[:Links]-+(b)
WHERE a._id IN ['Zenith', 'Arcadia'] AND b._id IN ['Eldoria', 'Nebula']
RETURN p
结果：p
本查询获取Arcadia与图中其他每个城市间的一条最短路径：
MATCH p = SHORTEST 1 ({_id: 'Arcadia'})-{1,10}()
RETURN p
在图中，Arcadia可以到达除Nexis外的8个城市（包括自己），以下是一种可能的返回结果：
