图路径搜索与最短路算法工程化

引言

「从 A 到 B 怎么走最近」是图上最古老也最实用的问题：导航算路、资金链路追溯、网络路由、供应链调拨、任务依赖的关键路径，最后都会归结为在带权图上找一条代价最小的路径。教科书里 Dijkstra 二十行就能写完，但把它放到生产环境就会撞上一连串工程问题：图有上亿条边，一次全展开内存就爆；权重是动态的（路况、汇率、时效），预处理加速结构全部失效；用户要的不只是一条最短路，而是三条互不相同的备选路线；有些边的权重是负数（返现、补贴、时间倒流语义），Dijkstra 直接给出错误答案却不报错；更常见的是启发式函数随手一写，A* 于是变成「看起来更快但结果不是最优」的玄学算法。本文按工程视角重新梳理路径搜索：先讲问题分类与约束，再讲 Dijkstra 的实现细节与提前终止、A* 的可采纳性与一致性、双向搜索与剪枝、预处理加速（Landmark 与 Contraction Hierarchies）、Yen K 短路、超大规模图的近似与并行策略，最后是 Cypher/GDS 中的落地写法与排错调优。目标：你能根据图的规模、权重是否动态、要几条路径、延迟预算来选对算法，并知道每个优化手段在什么条件下会失效。

前置：图算法实战 、深度路径遍历优化 、性能调优 。

目录

• 1. 问题分类与工程约束
• 2. Dijkstra 的工程实现
• 3. A* 与启发式设计
• 4. 双向搜索与剪枝
• 5. 预处理加速：Landmark 与 CH
• 6. Yen K 短路
• 7. 超大规模图的近似策略
• 8. 在 Cypher 与 GDS 中落地
• 9. 排错与调优
• 10. 速查表
• 延伸阅读

1. 问题分类与工程约束

先分清问的是哪一类最短路：

SSSP（单源最短路）：一个起点到所有点的距离 → 需要跑满全图
单源单汇：起点到指定终点 → 可提前终止，快得多
P2P（单对最短路）：一次查询一个起终点 → 导航/算路的主战场
APSP（全对最短路）：任意两点间距离 → 预计算，n² 空间，只适合小图
K 短路：前 K 条互不相同的路径 → 备用路线/容灾方案

按权重性质再分一层：

无权图     → BFS（O(m)），别用 Dijkstra
非负权     → Dijkstra（O(m log n) 堆实现）
0/1 权     → 0-1 BFS（双端队列，O(m)）
负权无负环 → Bellman-Ford（O(nm)）/ SPFA（最坏仍 O(nm)）
负环       → 无解，只能检测
动态权重   → 无法预处理，只能在线算

工程约束才是真正的决策依据：

1. 延迟预算：p99 是 10ms 还是 1s？决定能不能在线跑全图
2. 内存预算：一次查询允许占多少内存？决定能不能保留全路径
3. 权重动态性：多久变一次？变了要不要重建预处理结构
4. 结果语义：要一条还是要 K 条？要距离还是要完整路径？
5. 精度要求：精确最优还是可接受近似（1% 误差换 100 倍速度）
→ 先答这五个问题，再谈算法；复杂度表不是选型依据

心智：路径搜索的选型由「规模 + 权重动态性 + 延迟预算 + 精度要求」四个约束决定，而不是由算法复杂度表决定；静态大图才值得上预处理结构，动态权重图只能在线上做双向搜索加剪枝。

2. Dijkstra 的工程实现

核心不变量：已出堆的节点，其距离已确定，不会再被更新。

import heapq

def dijkstra(adj, src, dst=None):
    """adj: {u: [(v, w), ...]}；dst 非空时到达即终止"""
    dist, prev = {src: 0}, {src: None}
    heap, done = [(0, src)], set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in done:                    # 惰性删除：跳过过期堆项
            continue
        done.add(u)
        if dst is not None and u == dst:
            return d, rebuild(prev, dst)
        for v, w in adj.get(u, ()):
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v], prev[v] = nd, u
                heapq.heappush(heap, (nd, v))   # 允许重复入堆
    return (dist.get(dst) if dst else dist), None

def rebuild(prev, dst):
    path, cur = [], dst
    while cur is not None:
        path.append(cur); cur = prev[cur]
    return path[::-1]

为什么用「重复入堆 + 惰性删除」：二叉堆不支持 decrease-key（heapq 更没有），重复入堆最多 m 个堆项、空间 O(m)，出堆时用 done 过滤过期项即可，逻辑最简单；斐波那契堆理论 O(m + n log n) 但常数大、实现复杂，稀疏图上常打不过「二叉堆 + 惰性删除」。提前终止是最大的免费加速：单对查询到达终点即返回，通常只扩展全图的百分之几；只有问「到所有点的距离」时才不能停。负权必须显式拒绝：Dijkstra 的贪心正确性建立在边权非负之上，一条 -5 的边会让「已出堆即确定」的不变量失效，结果错误却不报错——导入阶段就要用约束或校验拦掉 w < 0 的关系，确实需要负权时换 Bellman-Ford / Johnson 并在文档写明。无向图别存两条独立关系：Neo4j 的关系天然有方向，无向遍历用 -[:ROAD]- 即可，物理存双向边只会让边数翻倍、每跳多一次 IO，只有「单向且反向权重不同」才需要两条。

心智：Dijkstra 的工程实现三件事——二叉堆配惰性删除（别惦记 decrease-key）、单对查询必开提前终止、负权必须在写入阶段拦掉；正确性来自非负权不变量，破坏它不会报错只会算错。

3. A* 与启发式设计

A* = Dijkstra + 方向感：把优先级从 g(u) 换成 f(u) = g(u) + h(u)，其中 g 是起点到 u 的真实代价，h 是 u 到终点的估计代价。

import heapq

def astar(adj, src, dst, h):
    """h(u) 必须是「u 到 dst 的代价下界」，否则结果不是最优"""
    g, prev = {src: 0}, {src: None}
    heap, done = [(h(src), 0, src)], set()
    while heap:
        _, gc, u = heapq.heappop(heap)
        if u in done:
            continue
        done.add(u)
        if u == dst:
            return gc, rebuild(prev, dst)
        for v, w in adj.get(u, ()):
            ng = gc + w
            if ng < g.get(v, float('inf')):
                g[v], prev[v] = ng, u
                heapq.heappush(heap, (ng + h(v), ng, v))
    return None, None

两个性质决定 A* 是否可靠：

可采纳性（admissible）：h(u) ≤ 真实代价 → 保证结果最优
一致性（consistent）：h(u) ≤ w(u,v) + h(v) → 保证每个点只扩展一次
→ 一致性更强且蕴含可采纳；不一致但可采纳的 h 仍能得到最优解，
  只是可能重复扩展节点（要配合 done 集合与距离比较）
→ 工程上优先设计一致的 h：它让「出堆即确定」继续成立

常见启发式的下界构造：欧氏距离（导航，直线距离 ≤ 路网距离，天然一致）；曼哈顿距离（仅 4 邻接网格可采纳）；ALT（Landmark，h(u) = max_L |d(L,u) - d(L,dst)|，由三角不等式保证可采纳，比欧氏紧得多）；预计算下界表（把地图切格，预存格心到终点的距离下界）。h 越紧，扩展的节点越少；h 恒为 0 就退化成 Dijkstra。 两个隐蔽陷阱：缩放 h 会破坏最优性——把 h 乘 1.2 就不再是下界，这在导航里叫「加权 A*」，牺牲最优性换速度，必须显式标注，业务要求真正最短路时绝不允许；权重单位必须统一——距离（米）与时间（秒）混用会让 h 失去意义，多目标权重（时间 + 费用 + 风险）要先归一化或线性组合，且 h 必须对组合后的目标函数取下界。

心智：A* 的正确性完全押在 h 上：h 必须是真实代价的下界（可采纳），最好还是一致的；欧氏距离、ALT 地标、格子下界表都是常用构造；缩放 h 会破坏最优性，只在下游明确接受近似时才允许。

4. 双向搜索与剪枝

原理：从起点正向扩展、从终点反向扩展，两边在中间相遇。在平均度数 d、最优路径长度 k 的图上，单向约 d^k，双向约 2·d^(k/2)——开方级的加速。

import heapq

def bidir(adj, radj, src, dst):
    if src == dst:
        return 0, [src]
    df, db = {src: 0}, {dst: 0}
    hf, hb = [(0, src)], [(0, dst)]
    donef, doneb = set(), set()
    best, meet = float('inf'), None

    def relax(h, dmap, dmap2, done, edges, other, nd, v, u):
        """统一的正/反向松弛：更新距离，并在对面已到达时更新接合点"""
        nonlocal best, meet
        if nd < dmap.get(v, float('inf')):
            dmap[v] = nd
            heapq.heappush(h, (nd, v))
        if v in other and nd + other[v] < best:
            best, meet = nd + other[v], v

    while hf and hb:
        if hf[0][0] + hb[0][0] >= best:   # 关键终止条件
            break
        if hf[0][0] <= hb[0][0]:
            d, u = heapq.heappop(hf)
            if u in donef:
                continue
            donef.add(u)
            for v, w in adj.get(u, ()):
                relax(hf, df, db, donef, adj, db, d + w, v, u)
        else:
            d, u = heapq.heappop(hb)
            if u in doneb:
                continue
            doneb.add(u)
            for v, w in radj.get(u, ()):
                relax(hb, db, df, doneb, radj, df, d + w, v, u)
    return best, meet

终止条件写错是双向搜索最经典的 bug：错误写法是「任一方向的堆顶 ≥ best 就停」，后果是另一方向可能还存在更优的接合点，返回的不是最短路；正确写法是两堆顶之和 ≥ best 才能停——因为正向剩余 ≥ hf[0]、反向剩余 ≥ hb[0]，任何未探索的接合点总代价 ≥ 两者之和。剪枝三件套：早停（只问一条路径时接合点确定即可停）；半径限制（已知可行解 U 后丢弃 g > U 的堆项，U 可由一次贪心或双向 BFS 先行给出）；方向裁剪（正向只沿出边、反向只沿入边，绝不来回横跳）。三者叠加能把导航级查询从「全图」压到「走廊状」的探索区域。反向图要显式维护：Neo4j 里 <()-[r]-() 反向遍历是原生的，但导出到外部内存计算（numpy/CSR）时必须同时建正向与反向 CSR，否则反向扩展退化成一维扫描。

心智：双向搜索把 d^k 压成 2·d^(k/2)，是「单对最短路」性价比最高的优化；但终止条件必须是「两堆顶之和 ≥ 当前最优」；配合早停、半径上界、方向裁剪，探索区域能从全图收缩到一条走廊。

5. 预处理加速：Landmark 与 CH

预处理换查询：把计算从「每次查询」搬到「一次预计算」，只适合静态图（权重基本不变）。

Landmark（ALT）：
  预选 L 个地标（度数高或覆盖广），预计算每个地标到所有节点的距离
  查询时 h(u) = max_L |d(L,u) - d(L,dst)|，由三角不等式保证可采纳
  预处理 O(L·m log n)，可增量加地标；L 取 8~16 即可，地标要分散
  缺点：L 次全图 Dijkstra 不便宜，只对「大量随机起终点查询」划算

Contraction Hierarchies（CH）：
  按「重要性」顺序逐个收缩节点：把经过该节点的最短路以捷径
  （shortcut）边保留，然后删掉该节点；查询时只在「上坡」方向
  做双向 Dijkstra，图规模缩到极小
  节点重要性：边数少、层级低、独立集大的节点先收缩
  捷径：收缩 v 时若 u→v→w 是 u 到 w 的唯一最短路，则加边 u→w
  缺点：只支持静态权重，图变了要重建；小世界图（社交、资金）
        收缩效果差，捷径可能爆炸（边数翻数倍）

什么时候不该上预处理：

1. 权重动态：路况/汇率/时效每次变 → 捷径全部失效
2. 小世界图（平均路径长度 3~4）→ 双向搜索本身就够快
3. 查询模式多样、起终点不固定 → 预计算收益摊不开
4. 内存紧张：CH 的捷径可能让边数翻数倍
→ 判断标准：查询量 × 加速比 > 预处理成本 + 重建成本，才值得

GDS 提供的是在线最短路：

// GDS 不做 CH 预处理，只提供 Dijkstra/A*/Yen 的在线计算
CALL gds.shortestPath.dijkstra.stream('roadGraph', {
  sourceNode: $src, targetNode: $dst,
  relationshipWeightProperty: 'length'
})
YIELD totalCost, nodeIds
RETURN totalCost, [n IN nodeIds | n.id] AS nodeIds;

GDS 适合中等规模、权重动态、查询量适中的场景；
亿级边的静态路网想要 CH 级性能，得用专门的路径规划引擎，
或把 CH 预处理结果作为捷径关系写回图里、查询时直接走捷径
→ 别指望图数据库同时给你 OLTP 查询和 CH 级算路

心智：预处理加速（ALT/CH）的本质是「用一次性的全图计算换每次查询的极速」，代价是只支持静态权重；路网类静态大图值得，小世界图与动态权重图不值得；图数据库的在线最短路适合中等规模与动态权重。

6. Yen K 短路

问题：找前 K 条互不相同的路径（备用路线、容灾方案）。注意「不同」指路径不同，不是距离不同。

Yen 的思路：在第 k 条路径上依次「偏离」——固定前 i 个节点作为根，从第 i 个节点出发找一条不含「已用过的边」、也不经过「根路径上节点」的最短路（spur path），拼起来成为一个候选。

def yen_k_shortest(adj, src, dst, K):
    first = dijkstra_path(adj, src, dst)      # 第 1 条：普通最短路
    if first is None:
        return []
    A, B = [first], []                        # A 结果集，B 候选堆
    for k in range(1, K):
        prev_path = A[k - 1]
        for i in range(len(prev_path) - 1):
            spur, root = prev_path[i], prev_path[:i + 1]
            root_cost = path_cost(adj, root)
            # 屏蔽集合：只屏蔽「与当前 root 前缀相同」的已确定路径用过的下一条边
            banned = {(p[i], p[i + 1]) for p in A
                      if p[:i + 1] == root and len(p) > i + 1}
            spur_path = dijkstra_path(adj, spur, dst,
                                      banned_edges=banned,
                                      blocked_nodes=set(root[:-1]))
            if spur_path:
                cand = root[:-1] + spur_path
                cost = root_cost + path_cost(adj, spur_path)
                if not any(c[0] == cand for c in B):   # 候选去重
                    heapq.heappush(B, (cost, cand))
        if not B:
            break
        _, best = heapq.heappop(B)
        A.append(best)
    return A

实现里的三个坑：候选去重（不同 (i, spur) 组合可能生成同一条路径，必须比对节点序列）；屏蔽集合的范围（屏蔽过头会漏掉合法路径，屏蔽不足会生成重复路径）；无环约束（默认求简单路径，允许环路时 K 短路会退化成「绕圈最短路」，结果无意义）。复杂度 O(K · n · (m + n log n))，K 大时明显变慢，K 取 3~5 足够。

没有 Yen 支持时的近似写法：

// allShortestPaths 只返回「等长」路径，不是严格 K 短路
MATCH (a:Node {id: $src}), (b:Node {id: $dst})
MATCH p = allShortestPaths((a)-[:LINK*..8]->(b))
RETURN [n IN nodes(p) | n.id] AS route, length(p) AS hops
ORDER BY hops ASC LIMIT 5;

真正的 K 短路用 GDS：CALL gds.shortestPath.yens.stream('g', {...})
业务只要「几条明显不同」的路线时，可退而求其次：
  用节点屏蔽法跑多次最短路，每次屏蔽上次路径的中间节点
  虽不保证是严格的前 K 条，但足够给出可用备选

心智：Yen K 短路 = 在已确定路径上依次「偏离」，每次固定根前缀 + 找一条屏蔽了已用边的 spur 最短路；实现难点是候选去重、屏蔽集合范围、无环约束；K 取 3~5，不要贪大。

7. 超大规模图的近似策略

当图大到「一次双向 Dijkstra 都跑不完」时，只能放弃精确最优，换近似或预计算索引。

1. 跳数限制 + 贪心：限制最多 k 跳，每跳选「启发式最优」的边
   代价：不保证最优；收益：O(k·d) 时间，延迟可预测
   适用：只需要「一条还行的路径」且延迟极敏感

2. 2-hop 覆盖（可达性索引）：
   为每个节点预存一组「枢纽」，使任意可达对 u→v 都存在枢纽 w
   同时出现在 u 的出集和 v 的入集中；查询变成集合求交，O(索引大小)
   代价：索引构造是 NP 难，只能用近似算法，空间可能远大于原图
   适用：只问「是否可达」不问「具体路径」

3. 双向 BFS + 采样：两端各做有界 BFS，在重叠层找接合点
   代价：不保证最优；收益：确定性的延迟上界

4. 并行/分布式 Dijkstra：
   delta-stepping 按距离分桶、桶内并行松弛；分布式按分区并行扩展
   代价：通信开销大，图分区质量决定成败（幂律图易倾斜）

分层图（Highway Hierarchy）是工业界的常用折中：按重要度给边打层级（高速 > 主干 > 支路），算长距离时先在高层级图（节点少）上跑，进入起终点区域后再下沉补细节。它既不是纯预处理（层级可增量更新）也不是纯在线（利用了结构），本质是把「图的天然分层」显式建模，比 CH 更适应半动态权重。近似策略的评估口径：质量（与精确解的平均误差与 p99 最坏误差）、延迟（p50/p99/最大值，是否与图规模相关）、空间（索引 / 原图）、更新成本（图变了索引要重建多少）。只报平均误差是耍流氓——路径规划里 p99 误差才是用户投诉来源。

心智：超大图的最短路只能在「精确但太慢」与「近似但可控」之间选：跳数限制 + 贪心最省事、2-hop 覆盖最适合可达性判断、delta-stepping 与分布式适合批量离线计算；评估近似必须看 p99 误差与延迟上界，而不是平均值。

8. 在 Cypher 与 GDS 中落地

原生 Cypher 最短路按跳数，不按权重：

// 无权最短路：跳数最少
MATCH (a:City {name: $from}), (b:City {name: $to})
MATCH p = shortestPath((a)-[:ROAD*..15]->(b))
RETURN length(p) AS hops, [n IN nodes(p) | n.name] AS route;

关键认知：Cypher 的 shortestPath 是「按跳数」的
写 (a)-[:ROAD*]->(b) 得到的是边数最少的路径
业务说「最短」通常指「代价最小」，两者结果可能完全不同
→ 带权场景一律走 GDS，或在接口文档里显式说明「按跳数」

GDS 投影与带权最短路：

// 1. 投影：只保留需要的标签/关系/权重属性
CALL gds.graph.project('roadGraph', 'City',
  { ROAD: { properties: 'length' } });

// 2. 单对带权最短路
CALL gds.shortestPath.dijkstra.stream('roadGraph', {
  sourceNode: $srcId, targetNode: $dstId,
  relationshipWeightProperty: 'length'
})
YIELD totalCost, nodeIds, costs
RETURN totalCost,
       [i IN range(0, size(nodeIds)-1) | {node: nodeIds[i], cost: costs[i]}] AS step;

// 3. A*（用 lat/lon 作启发式坐标）
CALL gds.shortestPath.astar.stream('roadGraph', {
  sourceNode: $srcId, targetNode: $dstId,
  relationshipWeightProperty: 'length',
  latitudeProperty: 'lat', longitudeProperty: 'lon'
})
YIELD totalCost, nodeIds RETURN totalCost, nodeIds;

// 4. K 短路
CALL gds.shortestPath.yens.stream('roadGraph', {
  sourceNode: $srcId, targetNode: $dstId,
  relationshipWeightProperty: 'length', k: 3
})
YIELD index, totalCost, nodeIds RETURN index, totalCost, nodeIds;

权重属性必须是数值且非负：GDS 投影时权重若为 null 会被当作不可用或默认 0，字符串权重会报错或忽略，负权会让 Dijkstra 结果不可信、A* 的 h 失去意义——导入阶段就要做质量检查：

MATCH ()-[r:ROAD]->()
WHERE r.length IS NULL OR r.length < 0
RETURN count(r) AS bad_edges;

投影图的复用与释放：GDS 投影图常驻内存，重复投影会报「图已存在」，生产写法用 gds.graph.exists 判断或先 gds.graph.drop；查询量大的服务应「一次投影、长期复用」，而不是每次请求都 project（投影本身就是全图扫描）；权重属性变了必须重新投影，GDS 不支持原地改属性。

心智：Cypher 原生 shortestPath 按跳数而非权重，带权必须走 GDS；GDS 走「投影图 + 在线算法」，投影一次长期复用；权重属性的 null 与负值会静默出错，必须在导入阶段拦。

9. 排错与调优

PROFILE 看三件事：

PROFILE
MATCH (a:City {name: $from}), (b:City {name: $to})
MATCH p = shortestPath((a)-[:ROAD*..15]->(b))
RETURN length(p);

1. 起点是否用索引定位：dbHits 只有 1~2 次才对
   → AllNodesScan 说明标签/属性索引缺失，起点是扫全表找的
2. 展开的中间结果规模：rows 是否在某一跳突然放大
   → 变长路径无上界时最容易在这里爆
3. 是否展开后才过滤：Filter 出现在 Expand 之后说明过滤太晚
   → 把能提前的谓词写进模式里

常见性能杀手：起点无索引（最短路前先做一次 AllNodesScan）；无上界变长路径（(a)-[:ROAD*]->(b) 在高扇出图上失控）；权重过滤写在返回后（先展开全部路径再过滤，白算）；超节点（起点/终点恰好是连接上万条边的枢纽）；频繁投影（每次请求都 gds.graph.project）；返回完整路径（只要距离就别 RETURN path）。逐条核对，通常前两条就能解释大部分慢查询。

超时与资源保护（四层）：查询级超时（dbms.transaction.timeout 兜底，防止一次查询拖垮实例）；路径深度上界（*..15 里的 15 是硬性保护而非装饰）；结果行数限制（K 短路与 allShortestPaths 必须配 LIMIT）；只读路由（最短路查询走只读副本，别占主库写入通道），热点起终点对可缓存但要考虑权重动态性导致的失效。验证正确性的手段：对拍（同一图用 Dijkstra 与双向 Dijkstra 交叉验证）；边界用例（src == dst、不可达、单节点图、零权边）；性质检查（h 可采纳时 A* 与 Dijkstra 结果必须一致）；负权扫描（导入后扫一遍是否有 w < 0）——「结果看起来合理」不是验证，对拍才是。

心智：最短路排错先看 PROFILE 三件事（起点是否走索引、rows 哪跳放大、是否展开后才过滤）；性能杀手集中在无索引起点、无上界变长路径、超节点、频繁投影；生产必须有超时、深度上界、LIMIT 与只读路由四层保护。

10. 速查表

全篇速查：

一句话记忆：路径搜索的选型由规模、权重动态性、延迟预算、精度要求四个约束决定；无权用 BFS，非负权用 Dijkstra（二叉堆 + 惰性删除 + 单对早停），负权必须在写入阶段拦掉否则静默算错；A* 的加速完全押在可采纳且一致的启发式上（欧氏距离、ALT 地标），缩放 h 会破坏最优性；双向搜索把 d^k 压成 2·d^(k/2) 但终止条件必须是「两堆顶之和 ≥ 当前最优」；ALT 与 Contraction Hierarchies 用预处理换查询极速，只适合静态权重的路网类大图，小世界图与动态权重图不值得；Yen 算法通过「根前缀 + 屏蔽已用边的 spur 最短路」求前 K 条不同路径，难点在候选去重与无环约束；亿级图的精确最短路不现实，只能上跳数限制、2-hop 可达性覆盖、delta-stepping 并行，并用 p99 误差而非平均值评估质量；落到 Cypher/GDS 时牢记 shortestPath 按跳数、带权走 GDS 投影、权重属性的 null 与负值会静默出错。

延伸阅读

• 图算法实战：最短路径、社区发现与 PageRank
• 深度路径遍历优化：变长路径、遍历器与剪枝
• 图查询优化与执行计划
• 图数据库性能调优
• 图数据库专题 — 全部图技术文章