如何使用Memgraph与MAGE实现多最短路径查找（Yen/Dijkstra/Star算法）

环境前提 #

• 已安装并运行Memgraph，且加载了MAGE插件（Memgraph默认集成MAGE，无需额外安装）
• 通过mgconsole或Memgraph Lab连接到Memgraph实例

1. 用Dijkstra算法获取多条等权重最短路径 #

Dijkstra默认返回单条最短路径，若存在多条权重相同的最短路径，可通过以下方式批量获取：

步骤1：构建示例加权图 #

CREATE (a:Node {id: 'A'}), (b:Node {id: 'B'}), (c:Node {id: 'C'}), (d:Node {id: 'D'}),
       (a)-[:CONNECTS {weight: 1}]->(b), (a)-[:CONNECTS {weight: 3}]->(c),
       (b)-[:CONNECTS {weight: 1}]->(c), (b)-[:CONNECTS {weight: 5}]->(d),
       (c)-[:CONNECTS {weight: 2}]->(d);

步骤2：查询所有等权重最短路径 #

// 先获取最短路径的权重值
WITH dijkstra.get_shortest_path((n:Node {id: 'A'}), (n:Node {id: 'D'}), 'weight') AS shortest_result
WITH shortest_result.total_weight AS min_weight

// 筛选所有总权重等于min_weight的路径
CALL apoc.path.allSimplePaths(
  (start:Node {id: 'A'}),
  (end:Node {id: 'D'}),
  {relationshipFilter: 'CONNECTS>', weightProperty: 'weight', maxWeight: min_weight}
) YIELD path

// 计算每条路径的总权重并过滤
RETURN path, reduce(total = 0, rel IN relationships(path) | total + rel.weight) AS total_weight
WHERE total_weight = min_weight;

2. 用Yen算法直接获取k条最短路径 #

Yen算法专门用于生成两点间的前k条最短路径（包含权重递增的路径），MAGE已内置该算法模块，是实现多最短路径查找的最优方案：

CALL yen.k_shortest_paths(
  (start:Node {id: 'A'}),
  (end:Node {id: 'D'}),
  'weight',  // 边的权重属性名
  3          // 指定要获取的路径数量k
) YIELD path, total_weight
RETURN path, total_weight
ORDER BY total_weight;

该查询会返回从A到D的前3条最短路径，自动按权重从小到大排序，且会自动处理路径重复问题。

3. 用A*算法实现启发式多最短路径查找 #

A*算法适合带启发函数的场景（比如地理路径规划），若要获取多条等权重最短路径，可参考Dijkstra的筛选逻辑：

步骤1：给节点添加启发式属性（如坐标） #

MATCH (n:Node)
SET n.x = CASE n.id
  WHEN 'A' THEN 0 WHEN 'B' THEN 1 WHEN 'C' THEN 2 WHEN 'D' THEN 3
END,
n.y = CASE n.id
  WHEN 'A' THEN 0 WHEN 'B' THEN 0 WHEN 'C' THEN 0 WHEN 'D' THEN 0
END;

步骤2：用A*查询最短路径并筛选多条结果 #

// 获取A*计算出的最短路径权重
WITH a_star.get_shortest_path(
  (n:Node {id: 'A'}),
  (n:Node {id: 'D'}),
  'weight',
  (node) -> (abs(node.x - 3) + abs(node.y - 0))  // 曼哈顿距离启发函数，终点D的x=3,y=0
) AS shortest_result
WITH shortest_result.total_weight AS min_weight

// 筛选所有总权重等于min_weight的路径
CALL apoc.path.allSimplePaths(
  (start:Node {id: 'A'}),
  (end:Node {id: 'D'}),
  {relationshipFilter: 'CONNECTS>', weightProperty: 'weight', maxWeight: min_weight}
) YIELD path

RETURN path, reduce(total = 0, rel IN relationships(path) | total + rel.weight) AS total_weight
WHERE total_weight = min_weight;

关键注意事项 #

• Dijkstra和Yen算法要求边的权重为非负数，若存在负权重需使用Bellman-Ford算法
• 为提升大型图的查询效率，建议给节点属性创建索引，例如：CREATE INDEX ON :Node(id);
• MAGE的算法模块默认随Memgraph安装，若自定义编译Memgraph需确保MAGE已集成

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