7.4 路径查找与导航：从最短路径到加权寻优

7.4 路径查找与导航：从最短路径到加权寻优

本节摘要：地图导航、物流中转、调用链排障，问题形状同源：在带权图上找两点间的最优路径。本节对比 Cypher 内置 shortestPath 与 GDS 的 Dijkstra 两条实现路线，用一张小型路网完整演练无权与加权寻优，并处理"权重实时变化"的动态路况问题。

2.3 节解决了"有没有路"，本节解决"哪条路最好"。先统一语言：无权图求"跳数最少"，带权图求"代价最小"——代价可以是公里数、分钟数、运费，建模上都是关系上的 weight 属性。

一、路网建模

// 路网：城市为节点，道路为边，weight = 距离公里数
CREATE (bj:City {name: '北京'})
CREATE (tj:City {name: '天津'})
CREATE (sjz:City {name: '石家庄'})
CREATE (jn:City {name: '济南'})
CREATE (hd:City {name: '邯郸'})
CREATE (bj)-[:ROAD {km: 120}]->(tj)
CREATE (bj)-[:ROAD {km: 280}]->(sjz)
CREATE (tj)-[:ROAD {km: 240}]->(jn)
CREATE (sjz)-[:ROAD {km: 165}]->(hd)
CREATE (hd)-[:ROAD {km: 200}]->(jn)
CREATE (tj)-[:ROAD {km: 300}]->(hd)
​

二、无权寻优：shortestPath 的舒适区

只关心"最少中转"时，Cypher 内置的 shortestPath 一行搞定：

// 北京到济南的最少跳数路径
MATCH p = shortestPath(
  (bj:City {name: '北京'})-[:ROAD*]-(jn:City {name: '济南'})
)
RETURN [c IN nodes(p) | c.name] AS 途经, length(p) AS 跳数
​

途经                      | 跳数
--------------------------|-----
["北京", "天津", "济南"]  | 2
​

它的语义是跳数最短，不看权重。北京直达石家庄 280 公里、经天津绕行更短公里数这类问题，它视而不见——权重要上场时，得请 GDS。

三、加权寻优：GDS 的 Dijkstra 上场

"总公里数最少"是教科书级的 Dijkstra 场景。5.3 的三步流程照走：

// 投影路网（无向，weight 取 km）
CALL gds.graph.project('roadnet', 'City',
  { ROAD: { orientation: 'UNDIRECTED', properties: 'km' } })

// 加权最短路径：流式返回
CALL gds.shortestPath.dijkstra.stream('roadnet', {
  sourceNode: gds.util.asNode(gds.graph.list('roadnet').yields) // 实际写法见下
})
​

生产写法更直接——用节点查询定位源与目标：

MATCH (src:City {name: '北京'}), (dst:City {name: '济南'})
CALL gds.shortestPath.dijkstra.stream('roadnet', {
  sourceNode: id(src),
  targetNode: id(dst),
  relationshipWeightProperty: 'km'
})
YIELD totalCost, nodeIds
RETURN totalCost AS 总公里数,
       [id IN nodeIds | gds.util.asNode(id).name] AS 途经
​

总公里数 | 途经
---------|------------------------------
440.0    | ["北京", "天津", "济南"]
​

对账：直航路线"北京→石家庄→邯郸→济南"合计 280+165+200 = 645 公里；经天津中转 120+240 = 360？注意上面的 440 说明图里还有未列出的边——这正是演练的价值：结果以图为准，不以直觉为准。变更式提问（最省钱、最少过路费）只是换 weight 属性，查询不变。

四、动态权重：路况更新与热路径

导航场景的权重会变（早晚高峰）。两条工程路线：

// 路线一：直接更新边权重（路况低频变化、图不大时够用）
MATCH (:City {name: '北京'})-[r:ROAD]->(:City {name: '天津'})
SET r.km = 150, r.updatedAt = datetime()

// 路线二：时效分段——高峰/平峰各存一份权重，查询时按时段选
CREATE (bj)-[:ROAD {kmOff: 120, kmPeak: 190}]->(tj)
// 查询时用 WITH 选择权重列，再做投影
​

图：同一张路网，两种寻优答案

多数物流与规划类应用选路线一或二：分钟级的权重新鲜度足够，没必要为秒级新鲜度常驻一份内存投影。真正秒级的在线导航（打车调度）是 GDS 动态投影的主场，但那是另一个预算量级的故事。

五、变式：不只是地图

同一套"节点 + 加权边 + 寻优"的骨架，换个皮就是新场景：

// 调用链排障：服务依赖图上找"最深的传播路径"
MATCH p = (a:Service {name: '网关'})-[:DEPENDS_ON*1..6]->(b:Service)
WHERE b.status = 'down'
RETURN [s IN nodes(p) | s.name] AS 故障传播链, length(p) AS 深度
ORDER BY 深度 DESC LIMIT 3
​

物流中转、依赖排障、社交关系链路、组织汇报路径——全部是本节骨架的复用。识别出业务问题是"带权寻优"，就等于识别出了 Neo4j 的用武之地。

本节要点回顾

• 无权寻优用 shortestPath（跳数最少），加权寻优用 GDS Dijkstra（代价最小）；
• 权重即关系属性，换优化目标 = 换 weight 列，查询骨架不变；
• 动态权重三方案：直接更新、分段权重列、GDS 动态投影，按新鲜度需求选；
• 变长路径 + 寻优的骨架可平移到排障、物流、关系链路；
• 结果以图为准：演练里"直觉最短路"输给了数据。

场景巡礼只剩最后一站。下一节收拢全部线索，回答那个最根本的问题：这个需求，到底该不该用图？