概述
两点间的最短路径是两点间边数最少的路径。使用以下路径选择前缀可从路径模式匹配结果中选择最短路径:
路径选择 |
描述 |
---|---|
ALL SHORTEST |
从每个分区选择所有最短路径 |
ANY SHORTEST |
从每个分区选择一条最短路径;非确定性选择 |
SHORTEST k |
从每个分区选择k [1]条最短路径;非确定性选择 |
SHORTEST k GROUP |
根据路径长度对路径进行分组并按长度升序排列,再从每个分区选择前k 组的所有路径;确定性选择 |
[1]k
:为非负整数。若路径数量少于k
,则保留全部路径。
当使用以上路径选择前缀时,路径约束强制使用TRAIL
。
暂不支持选择“最低开销”路径。“最低开销”路径与“最短”路径类似,但要求最小化路径总成本,即某项边权重(属性)和。如需此功能,可使用UQL的
ab()
或autonet()
查询。
最短路径暂不支持子路径变量。
示例图

CREATE GRAPH myGraph {
NODE City ({name strig}),
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
使用ALL SHORTEST
选择全部最短路径。
MATCH p = ALL SHORTEST (a)-{,10}(b)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p
结果:p

ANY SHORTEST
使用ANY SHORTEST
选择一条最短路径。
MATCH p = ANY SHORTEST (a:City)-{,10}(b:City)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p
结果:p

SHORTEST k
使用SHORTEST k
选择每个分区中k
条最短路径。
MATCH p = SHORTEST 2 (a:City)-{,10}(b:City)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p
结果:p

MATCH p = SHORTEST 3 (a:City)-{,10}(b:City)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p
由于Arcadia
和Eldoria
之间只有两条长度为2
的最短路径,因此需要再选择一条次短路径。本例中次短路径长度为3
,且只有1条,因此返回以下三条路径:

SHORTEST k GROUP
使用SHORTEST k GROUP
从每个分区选择获得全部最短到第k
短的路径。它根据路径长度对路径进行分组,并按长度进行升序排列,再从每个分区中选择前k
组的所有路径。
MATCH p = SHORTEST 3 GROUP (a:City)-[]-+(b:City)
WHERE a._id = 'Arcadia' AND b._id = 'Eldoria'
RETURN p
查询返回两条长度为2
的最短路径,一条长度为3
的次短路径,以及一条长度为4
的第三短路径:

分区
当路径模式匹配到多个起点和终点时,匹配结果会根据不同的起终点点对进行分区,随后在各分区中选择最短路径。
本查询中,首先对a
和b
进行笛卡尔积,随后变量a
和b
在最短路径模板中被引用,因此共有四条最短路径从四个分区中被选择后返回:
MATCH p = SHORTEST 1 (a:City)-{,10}(b:City)
WHERE (a._id IN ['Zenith', 'Arcadia']) AND (b._id IN ['Eldoria', 'Nebula'])
RETURN p
结果:p

单源最短路径
本条查询获取Arcadia
和其他每个城市间的1条最短路径:
MATCH p = SHORTEST 1 (c1:City {_id: 'Arcadia'})-{,10}(c2:City)
WHERE c2._id <> c1._id
RETURN p
在本图里,Arcadia
可以到达除Nexis
外的7个城市。以下为可能的返回结果:
