如何在Cypher/Memgraph中查找包含指定节点列表的最短路径

原查询的问题分析 #

你原来的查询是先通过BFS匹配source到dest的路径，再过滤包含所有指定节点的结果，但这种方式存在两个核心问题：

1. BFS优先返回不经过额外节点的最短路径，这类路径大概率不包含所有指定节点，过滤后可能没有符合要求的结果；
2. 即使有结果，也无法保证是包含所有指定节点的最短路径——因为很多符合条件的路径在BFS层级中靠后，可能被提前截断或未被遍历到。

正确的实现思路 #

要确保路径包含所有指定节点，我们可以将问题拆解为：遍历指定节点的所有可能经过顺序，依次计算相邻节点间的最短路径并拼接，最终在所有拼接后的路径中选取总长度最短的一条。这种方法能保证每一段都是最短路径，拼接后的总长度也是符合要求的最优解。

调整后的Cypher查询 #

WITH collect(t) AS required_nodes, source, dest
// 生成所有必选节点的排列，覆盖所有可能的经过顺序
UNWIND PERMUTATIONS(required_nodes) AS permutation
// 构建完整的节点遍历序列：起点 → 必选节点（按排列顺序）→ 终点
WITH source + permutation + [dest] AS node_sequence, permutation
// 依次计算序列中相邻节点的最短路径段
REDUCE(path_agg = [], i IN range(0, size(node_sequence)-2) |
  path_agg + [shortestPath((node_sequence[i])-[:link*]-(node_sequence[i+1]))]
) AS path_segments
// 过滤掉存在无效路径段的情况（比如某两个节点间无连通路径）
WHERE ALL(seg IN path_segments WHERE seg IS NOT NULL)
// 合并所有路径段的节点和关系，构建完整路径
WITH [n IN REDUCE(nodes_agg = [], seg IN path_segments | nodes_agg + nodes(seg)) | n] AS all_nodes,
     [r IN REDUCE(rels_agg = [], seg IN path_segments | rels_agg + rels(seg)) | r] AS all_rels
WITH path(all_nodes, all_rels) AS full_path
// 去重：不同排列可能生成完全相同的完整路径
WITH DISTINCT full_path
// 按路径长度升序排序，取第一条即为最短路径
ORDER BY length(full_path) ASC
LIMIT 1
RETURN full_path, required_nodes

补充说明 #

• 如果指定节点的数量较多（比如超过5个），排列数会呈阶乘增长（n!），查询性能会下降。这种情况下可以考虑先通过MATCH path=(source)-[:link*]-(dest)匹配所有可能路径，再过滤包含所有指定节点的结果，最后按长度排序取最短，但这种方式在大图中效率较低；
• 确保source、dest和所有required_nodes都是连通的，否则查询会返回空结果；
• 若不需要去重，可以去掉WITH DISTINCT full_path这一步，但可能会返回多条重复的最短路径。

内容的提问来源于stack exchange，提问作者herzi