城市路径问题很多人觉得一定要调用地图服务才能解决或者至少要上A*算法才显得专业。我做这类需求的第一版原型时反而习惯先把广度优先搜索BFS跑通。不是因为BFS简单而是因为它足够可靠很多带约束的路径问题抽象之后就是一个无权图上求最短步数的问题这时候BFS就是正确答案。这篇文章记录的是我梳理城市路径问题时用BFS的完整思路包括算法原理、代码模板、网格地图上的完整实操以及我实际踩过的一些坑。1. 城市路径问题是怎么“翻译”成BFS的1.1 核心建模路网、节点和边先把问题变成图。我不关心每条路叫什么名字也不关心路两旁有什么商店我把路网中允许转向的交叉口抽出来当节点把两个路口之间的道路当边。BFS要求每条边的代价一致所以最直观的用法就是求“从A到B最少经过多少个路口”。有人说真实道路长度不一样怎么用BFS那就把长度做离散化或者先不要引入长度先求最少换乘、最少步数。这在很多业务里比最短距离更有价值。例如一个骑手在不同站点之间送单换乘次数少往往比距离短更重要。模型搭好后城市路径问题就变成“在无权图中求两个节点之间最短路径”的问题。如果地图是栅格化的也能建模成网格图。每个格子是一个节点上下左右相邻的通行格之间有边障碍物不算节点。这个模型在城市交通仿真、园区巡检、仓库拣货里很常见最重要的原因就是它简单、可解释、故障容易排查。1.2 为什么确定最短路要选BFS而不是DFSBFS是按层向外扩展的。从一个点出发把所有邻居放在同一层第二层是“邻居的邻居”第三层继续往后扩。这样先访问到某个节点的一定是层数最小的路径而层数就是步数。如果终点第一次出队那此时步数就是最短步数。有人问DFS也能找到路径但DFS会沿着一条道走到底第一次找到的路径不保证最短。Dijkstra可以处理加权图但需要优先队列复杂度更高A*更快但要有合适的启发函数。在城市路径问题里只要不需要加权BFS就是最稳妥的方案。这里整理一个快速对比算法适用场景能否保证步数最少主要开销BFS无权图、边权相等保证队列空间可能较大DFS连通性判断、遍历不保证递归栈或显式栈Dijkstra带权图最短路径按权值保证优先队列A*带权图且启发信息好启发函数满足条件时可以保证优先队列加启发计算所以我常跟项目里的同事说BFS不是所有场景的银弹但在无权路径问题上别一上来就堆复杂算法。1.3 邻接表还是网格影响写代码的方式城市道路交叉口适合用邻接表存图每个节点对应一份邻居列表网格地图适合用二维数组加上方向数组。两种方式都能跑BFS区别在于邻居怎么生成。邻接表直接遍历列表网格则要根据坐标计算上下左右的邻居。我自己的习惯是只要原始数据里有明确的“道路段”关系就用邻接表如果是像素化地图或栅格扫描出来的数据就用网格。后面第3部分的实操例子就是用网格来演示因为它最能暴露边界问题。2. BFS 运行的底层逻辑与模板代码2.1 队列怎么把“层”带出来BFS用队列实现队列是先进先出的结构。起始点先入队然后循环从队头弹出节点把没访问过的邻居依次放进队尾。这样先入队的节点总是先被处理同一层的节点会在下一层节点之前被弹出。如果你把队列想象成一层水波每次弹出当前层的一个点就会把下一层的新点放到队尾。等当前层全部处理完队首自然就轮到下一层。这个“层”的概念正好对应路径长度。我见过不少人用递归方法写深度优先遍历很熟练一到BFS就卡壳。实际上只要抓住“队列里放的是待处理节点”这一点代码就不会跑偏。每弹出一个节点它的步数等于前一个节点的步数加一。2.2 一个可以直接改的Python模板下面这个模板是最一般形式适用于邻接表图。它同时完成了最短距离求解、路径记录和路径重建from collections import deque def bfs_shortest_path(graph, start, target): # graph: 字典键为节点值为邻居列表 queue deque([start]) visited {start} parent {start: None} while queue: node queue.popleft() if node target: path [] while node is not None: path.append(node) node parent[node] return path[::-1] for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) parent[neighbor] node queue.append(neighbor) return None这个模板有几个关键点。第一visited用集合查询快。第二parent字典记录每个节点的前一个节点终点一旦找到就沿着parent往回找路径。第三标记visited发生在邻居入队的那一刻不是等邻居出队才标记这一点非常重要后面第5部分我会专门讲。2.3 路径记录的原理和细节parent数组或字典的意义相当于每个节点上留一个“我来自哪里”的标签。中间过程不记录完整路径只记录前驱。这样空间占用少而且回溯时只需要从终点不断往回跳。但在网格场景中我更喜欢用二维数组来存parent这样坐标信息更直接。比如parent[nr][nc] (r, c)表示(nr, nc)是从(r, c)走过来的。回溯时从终点开始一路往前倒推直到起点然后把顺序反过来。很多新手会忽略一点不要在任何节点重复设置parent。如果某个节点已经被访问过就一定不要再去更新它的前驱否则路径会乱。因为BFS先访问到某个节点时前面那条路径已经是最短的后到的路径不可能更短。3. 实操过程在5×5城市网格上跑通BFS3.1 把网格地图转成程序能读的数据我拿一个虚构的5×5城市街区做例子。用0表示可通行的道路1表示建筑物或封闭区域。地图就长下面这样0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0起点放在左上角(0, 0)终点放在右下角(4, 4)。这个地图里有几栋“建筑”挡住了部分中间道路所以路径必须绕行。四方向移动规则是上下左右不能穿越建筑。为什么选四方向而不是八方向因为城市道路里车辆一般是沿道路方向行驶网格模型里的格子如果代表街区允许斜着穿过去就不符合现实。做园区路径规划时如果走的是室外草地或广场八方向也可以。这里我按车辆路径场景处理用四方向。3.2 完整代码和结果分析直接用以下Python代码就能跑通from collections import deque maze [ [0, 0, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 0, 0] ] start (0, 0) target (4, 4) rows, cols len(maze), len(maze[0]) visited [[False] * cols for _ in range(rows)] prev [[None] * cols for _ in range(rows)] visited[start[0]][start[1]] True queue deque([start]) directions [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上、下、左、右 found False while queue: r, c queue.popleft() if (r, c) target: found True break for dr, dc in directions: nr, nc r dr, c dc if 0 nr rows and 0 nc cols and not visited[nr][nc] and maze[nr][nc] 0: visited[nr][nc] True prev[nr][nc] (r, c) queue.append((nr, nc)) if not found: print(无可用路径) else: path [] cur target while cur is not None: path.append(cur) cur prev[cur[0]][cur[1]] path.reverse() print(最短路径节点序列:, path) print(步数:, len(path) - 1)运行后得到的结果类似最短路径节点序列: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)] 步数: 8这条路径的意思是起点往下走一格穿过第二行建筑左侧再从中间横穿过去从右侧往下到终点。步数是8也就是经过了8条路段。因为地图对称且障碍物位置不同实际路径可能会有两种选择但步数一定是8。3.3 从路径到导航指令路径是坐标序列但实际操作中我还要把它转换成指令。比如根据上一个坐标和当前坐标的差值判断是左转、右转还是直行instructions [] for i in range(1, len(path)): dr path[i][0] - path[i-1][0] dc path[i][1] - path[i-1][1] if dr -1 and dc 0: instructions.append(向上) elif dr 1 and dc 0: instructions.append(向下) elif dr 0 and dc -1: instructions.append(向左) elif dr 0 and dc 1: instructions.append(向右)这里得到的是一串“方向感”指令。如果要做成类似“前方路口右转”还得把连续同方向的路段合并成“直行经过几个路口”再结合道路名称信息但核心路径就已经由BFS给出来了。我建议在真实项目里把网格坐标和真实地理坐标做一个映射。比如每个格子对应一个经纬度范围或者对应一个楼层平面图编号这样BFS算出来的路径才能落到业务系统里。否则算法对了数据对接不上照样白干。4. 真实城市路网里BFS的常见改造方向4.1 双向BFS提速当图很大时单向BFS会访问很多无关节点。比如一个城市几万个路口从一端开始搜索可能要展开一大片区域才能碰到终点。双向BFS的思路是从起点和终点同时开始BFS两边交替扩展一层直到两个方向的访问区域相遇。搜索空间能降多少假设每个节点平均有b个邻居单向BFS从起点扩展到第d层时访问量大约是b^d量级。双向BFS从两头各扩展d/2层两边访问量大约是2 * b^(d/2)。在网格路口平均度比较大的情况下这个差距非常明显。代码框架也很容易改造def bidirectional_bfs(graph, start, target): if start target: return [start] q_start deque([start]) q_target deque([target]) visited_start {start} visited_target {target} parent_start {start: None} parent_target {target: None} while q_start and q_target: if expand_one_level(q_start, visited_start, visited_target, parent_start, graph): return reconstruct_path(...) if expand_one_level(q_target, visited_target, visited_start, parent_target, graph): return reconstruct_path(...) return None双向BFS实现起来比单向多不少细节尤其是两棵搜索树相遇后要拼接路径但性能提升是实打实的。我在一个几千节点的路网数据上测过单向BFS平均要访问两三千个节点双向通常只要几百个。4.2 边带权重的扩展0-1 BFS 与 Dijkstra城市道路越来越复杂不是每条路的代价都相等。快速路比小路省时间这时候要把边权加上。BFS无法处理权重不一样的边但有一个特殊情况可以用0-1 BFS边权只有0和1两种。比如“走普通路代价1走专用通道代价0”这时用双端队列遇到代价为0的边插到队首代价为1的边插到队尾仍然能保证最短路径复杂度接近BFS。一旦边权是任意正整数就要上Dijkstra。Dijkstra本质上就是把BFS的队列换成优先队列每次从当前已知代价最小的节点继续扩展。所以你可以认为BFS是Dijkstra在所有边权为1时的特例。如果项目里有实时路况、红绿灯延时我一般会先把原始数据整理成带权有向图再用Dijkstra。但业务指标如果是“换乘次数最少”权值全部等于1BFS反而是最优选择。选算法不是在炫技而是先看清约束条件。4.3 状态压缩与剪枝城市路径问题里有一种常见变种除了位置还要记住一些附加状态。比如骑手需要先取货再送货再比如AGV小车电量有限不能走太远。这类问题如果把“位置剩余电量已取货物”当成一个完整状态搜索空间会爆炸。BFS同样可以做状态压缩。不管附加状态有多少只要状态能编码成一个整数visited就可以用位运算来标记。比如一个二维坐标加上两个布尔状态可以压成一个整数值放进集合里判断是否访问过。剪枝也很关键。扩展节点前先算一下当前代价是否已经超过上限或者当前层数是不是已经超过已知最优解都可以省掉大量无效分支。我在处理带时间窗的路径Demo时就是在BFS基础上加了一个“当前步数剩余必到点数量”的下界超过就提前放弃速度提升很明显。5. BFS 实战中的常见坑与排查记录5.1 visited 到底是入队标记还是出队标记新手最容易犯的错就是等节点弹出队列时才标记visited。这样做会导致同一个节点被多次放进队列因为它的多个邻居可能都先看到了它。地图越大重复队列会越长甚至出现看起来像死循环的情况。正确做法是在节点被放入队列的那一刻就标记visited。这样后续其他节点再看到它时因为visited已经是True就不会重复入队。我在网上看过很多BFS写法有些在出队时标记也能跑但那通常是在每一步访问时没有重复依赖。为了保证性能和正确性入队标记是更稳妥的选择。5.2 路径回溯时最容易出错的点路径回溯的经典错误有三个。第一prev数组没有初始化或者起点没有预设为None回溯时不知道何时停止。第二回溯到起点后忘记反转列表导致输出路径是终点到起点。第三在找到终点后没有立刻中断搜索让后面的节点覆盖掉prev,导致路径信息丢失。我调试时一般会加一个辅助函数def print_path(path): for p in path: print(p)然后先用小地图手动验证。比如3×3地图肉眼能判断最短路径应该怎么走先跑通再换大数据。别直接上大路网否则出了问题根本看不出是算法问题还是数据问题。5.3 调试技巧和速查表调试BFS最有效的手段是在循环里打印队列状态和当前弹出节点但只适合小图。还可以维护一个level数组或字典每访问一个节点就记录层数。这样就算不回溯路径也能立刻看出终点是否在第几层找到。我整理了一张速查表方便排查问题现象可能原因处理方式访问到越界坐标没检查nr和nc的范围在访问前先做边界判断程序长时间不结束visited标记过晚或漏标改为入队时标记路径顺序是反的回溯后没有反转调用reverse()或用栈路径中间有断点parent被后续节点覆盖找到终点后立即break结果不是最短路径用了DFS思路或图不是无权确认每条边代价相等起点就是终点没考虑特殊情况开头直接判断start target5.4 先跑通再优化是BFS最稳的落地路径我始终建议先做一版最简单的单向BFS地图写死成小网格确认路径结果正确再逐步换成真实路网数据、加入双向BFS、再考虑换Dijkstra。这个过程中每一步都有对照结果出错能快速定位。直接上来就写双向BFS一旦路径拼不对排查成本会高很多。6. 写在最后几个实操体会我在实际项目里做公交换乘次数最少的问题时第一版就用的BFS。数据整理成邻接表后把“线路站点”当作节点只要两个站点在同一个可换乘集合里就连一条边。BFS跑出来的结果比当时团队里另一个人用Dijkstra跑的结果还快因为每条边代价本来都是1Dijkstra的优先队列完全用不上。还有一点BFS虽然基础但写起来也要注意迭代而不是递归。有些新手喜欢递归写法遇到环图很容易栈溢出。队列加循环是BFS最可靠的形式。最后分享一个小技巧如果你在调试网格BFS把地图、起点、终点都用字符打印出来访问过的点标记成.当前路径标记成*一眼就能看出搜索过程是怎么扩散的。路径算法这个东西跑通容易跑得明白才是真功夫。
