如何用Apache AGE的Cypher查询实现Dijkstra算法找城市最短路径

Apache AGE集成了Graph Data Science(GDS)库，可直接调用Dijkstra算法实现带权重（距离）的最短路径查询。以下是针对你的CITIES图的具体实现方案：

前提说明 #

假设你的图结构满足：

• 顶点标签为City，包含标识城市的属性（如name）
• 边类型为CONNECTED_TO（可替换为你实际的边类型），边的距离属性为distance

1. 查询单个城市对的最短路径 #

如果只需要计算特定两个城市（如北京到上海）的最短路径，使用以下查询：

SELECT *
FROM cypher('CITIES', $$
    MATCH (start:City {name: 'Beijing'}), (end:City {name: 'Shanghai'})
    CALL gds.shortestPath.dijkstra.stream({
        nodeProjection: 'City',
        relationshipProjection: {
            CONNECTED_TO: {
                type: 'CONNECTED_TO',
                properties: 'distance',
                orientation: 'UNDIRECTED' // 若为有向图，改为DIRECTED
            }
        },
        startNode: start,
        endNode: end,
        relationshipWeightProperty: 'distance'
    })
    YIELD totalCost, nodeIds
    RETURN
        [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS 路径城市列表,
        totalCost AS 总距离
$$) AS (path_cities agtype, total_distance agtype);

2. 查询任意两个城市间的所有最短路径 #

若需要遍历所有城市对计算最短路径，使用以下查询（注意：大图全量计算可能影响性能，建议按需添加过滤条件）：

SELECT *
FROM cypher('CITIES', $$
    MATCH (start:City), (end:City)
    WHERE start <> end // 排除起点和终点为同一城市的情况
    CALL gds.shortestPath.dijkstra.stream({
        nodeProjection: 'City',
        relationshipProjection: {
            CONNECTED_TO: {
                type: 'CONNECTED_TO',
                properties: 'distance',
                orientation: 'UNDIRECTED'
            }
        },
        startNode: start,
        endNode: end,
        relationshipWeightProperty: 'distance'
    })
    YIELD totalCost, nodeIds
    RETURN
        gds.util.asNode(nodeIds[0]).name AS 出发城市,
        gds.util.asNode(nodeIds[-1]).name AS 到达城市,
        [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS 路径,
        totalCost AS 总距离
$$) AS (origin agtype, destination agtype, path agtype, total_distance agtype);

关键参数说明 #

• nodeProjection: 指定参与计算的顶点标签
• relationshipProjection: 指定参与计算的边类型及权重属性，orientation控制边的方向
• relationshipWeightProperty: 指定作为路径权重的边属性（即你的距离属性）
• gds.util.asNode: 将节点ID转换为节点对象，用于提取城市名称等属性

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