PostgreSQL中求最少换乘路径，从递归CTE到pgRouting的实战对比

在数据库内直接求解图论问题——尤其是“换乘次数最少”这类带多目标排序的路径规划——曾长期被视为SQL的禁区。但随着PostgreSQL对递归查询和空间扩展的支持增强，这一场景正逐步进入工程实践视野。近期一篇技术复盘揭示了真实业务中从手写递归CTE转向专业图算法扩展的关键转折点：面对一个仅含40个站点、2条线路、2个换乘点的简化路网，开发者尝试用纯SQL求解1号站到39号站的最优路径，最终发现，递归CTE适合小规模穷举验证，而pgRouting才是生产级图查询的可靠选择。

该问题源于某本地生活平台的数据集建模：站点邻接表station_edges(from_id, to_id, distance_m)共80行记录，结构为两条线性链（1–20与21–40），通过10↔21、20↔30两个换乘点连接。目标是找出从1到39的路径，优先级为：①换乘次数最少；②相同换乘次数下总距离最短。理论上存在两条主路径：经10→21换乘（28段边）、或经20→30换乘（29段边），前者更优。

第一阶段：手写递归CTE的三次碰壁

作者首先采用WITH RECURSIVE实现深度优先搜索。初版SQL很快报错：integer与numeric类型不匹配——因from_id/to_id定义为BIGINT，而部分中间计算误用了整型字面量。修正后加入深度限制hops < 4，却导致永远无法抵达39号站：实际路径需经过28段边，即29个节点，深度限制过严直接剪枝了可行解。放宽至hops < 50后逻辑通了，但性能急剧恶化：递归CTE本质是穷举所有可能路径，时间复杂度接近O(b^d)（b为分支因子，d为深度）。在本例中虽仅40节点，已产生数千条路径；若扩展至真实城市路网（数千站点），计算将指数爆炸，且PostgreSQL递归CTE无法并行执行，单核瓶颈明显。

更关键的是，递归CTE生成的是“所有可达路径”，需后续用窗口函数（如ROW_NUMBER() OVER (ORDER BY transfers, total_dist)）二次筛选最优解，流程割裂、易出错。作者还指出，PG 14引入的SEARCH与CYCLE语法可提升可读性，但未改变其穷举本质。

第二阶段：切换pgRouting，Dijkstra算法立竿见影

当问题规模稍增，作者转向PostgreSQL的图计算扩展pgRouting。安装后，先将邻接表转换为标准边表（含id, source, target, cost字段），再调用pgr_dijkstra(edges, start_vid:=1, end_vid:=39)。结果在毫秒级返回：路径为1→2→…→10→21→…→39，共28段边、1次换乘、总距离27,568米（初期误读为秒，实为米）。该结果与理论预期一致，且无歧义。

pgRouting的高效源于其底层实现：Dijkstra算法使用优先队列（最小堆），每次扩展当前累积代价最小的节点，避免无效探索。其时间复杂度为O((V+E) log V)，远优于穷举。更重要的是，cost字段可抽象为任意权重——此处设为距离，但也可设为换乘惩罚值（如直达边cost=1，换乘边cost=10），从而将“换乘次数优先”编码进单一目标函数，无需多层排序。

为何递归CTE不适合图路径搜索？

文章明确划清了适用边界：递归CTE擅长处理层次化、有向无环、规模极小的遍历问题，例如组织架构树查询、文件系统路径展开；而图路径问题通常含环、规模中等以上、需优化目标函数，此时CTE的“生成全部再筛选”模式注定低效。其根本矛盾在于：SQL是声明式语言，而路径搜索是典型的命令式过程——需要动态决策“下一步去哪”，这正是Dijkstra等算法的核心机制。

值得一提的是，pgRouting不仅支持Dijkstra，还提供A*、KSP（k最短路径）、TSP等算法，可应对更复杂需求。对于超大规模图（如百万级节点），则需结合Neo4j、JanusGraph等原生图数据库，或采用分布式图计算框架（如Apache Giraph）。

延伸：从路径规划看数据库能力演进

该案例折射出数据库能力的深层变化。过去，图计算必须交由应用层（如Java内存中建图+BFS）；如今，PostgreSQL通过扩展生态（PostGIS、pgRouting、PG Vector）逐步覆盖空间、图、向量等非传统场景。这并非要取代专用系统，而是为中小规模、低延迟要求的业务提供“一站式”解决方案——尤其适合与现有OLTP流程集成，避免数据搬迁与系统耦合。

类似思路也见于其他优化实践。例如在骑手轨迹热力图生成中，作者曾对比两种六边形网格生成策略：全局网格+LEFT JOIN导致90%计算浪费，而CROSS JOIN LATERAL按需生成局部网格，将耗时从13.59秒降至5.81秒。其本质同样是避免全量膨胀，聚焦有效计算单元——这与Dijkstra“只扩展有希望的节点”异曲同工。

结语

一次看似简单的“求最少换乘路径”，暴露出SQL表达力与数据库执行引擎之间的鸿沟。递归CTE能“写出”路径搜索逻辑，却难以“高效执行”；而pgRouting通过封装成熟算法，将工程实现细节透明化，让开发者专注业务规则。对于数据工程师而言，理解何时该用声明式穷举、何时该借力专业扩展,已成为现代SQL能力的重要组成部分。在图数据日益普及的今天，掌握pgRouting等工具，或许比精通嵌套子查询更具实战价值。