如何用Python和Cypher在Apache Age中实现最短路径算法？

针对你的城市图结构，要查找从纽约到休斯顿的最短路径，推荐使用Apache Age支持的Cypher查询实现，分为**加权最短路径（距离总和最小）和非加权最短路径（节点数最少）**两种场景，以下是具体方案：

1. 加权最短路径（按距离总和最小） #

这是你的场景中更实用的需求，需要计算路径中所有边的distance属性总和，取最小值。

Python代码实现 #

from age import Age

age = Age()
# 省略你已有的节点和边创建代码...

# 执行加权最短路径查询
result = age.execute("""
MATCH (start:City {name: 'New York'}), (end:City {name: 'Houston'})
MATCH path = (start)-[:CONNECTED*]->(end)
WITH path, reduce(total = 0, rel IN relationships(path) | total + rel.distance) AS total_distance
ORDER BY total_distance ASC
LIMIT 1
RETURN path, total_distance, nodes(path) AS path_nodes, relationships(path) AS path_edges
""")

# 解析并打印结果
for record in result:
    print(f"最短路径总距离: {record['total_distance']}")
    print("路径节点顺序:")
    for node in record['path_nodes']:
        print(f"- {node['name']}")
    print("路径连接详情:")
    for edge in record['path_edges']:
        print(f"- {edge.start_node['name']} --({edge['distance']})-- {edge.end_node['name']}")

查询逻辑说明 #

• MATCH path = (start)-[:CONNECTED*]->(end)：匹配从纽约到休斯顿的所有可能路径，*表示任意长度的边
• reduce(total = 0, rel IN relationships(path) | total + rel.distance)：累加路径中每条边的distance，得到总距离
• ORDER BY total_distance ASC LIMIT 1：按总距离升序排序，取第一条即为最短路径

运行后输出示例：

最短路径总距离: 1653
路径节点顺序:
- New York
- Chicago
- Houston
路径连接详情:
- New York --(713)-- Chicago
- Chicago --(940)-- Houston

2. 非加权最短路径（节点数最少） #

如果只需节点数量最少的路径（不考虑距离），可使用Cypher内置的shortestPath函数：

Python代码实现 #

result = age.execute("""
MATCH (start:City {name: 'New York'}), (end:City {name: 'Houston'}),
      path = shortestPath((start)-[:CONNECTED*]->(end))
RETURN path, length(path) AS edge_count, nodes(path) AS path_nodes
""")

# 解析结果
for record in result:
    print(f"路径边数量: {record['edge_count']}")
    print("路径节点:")
    for node in record['path_nodes']:
        print(f"- {node['name']}")

说明 #

shortestPath函数直接返回节点数最少的路径，在你的图中这条路径同样是纽约->芝加哥->休斯顿，但如果存在节点数相同但距离不同的路径，结果会与加权查询有差异。

内容的提问来源于stack exchange，提问作者Muhammad Awais Bin Adil