前阵子接到一个需求要在网格上找一个最低成本路径从左上角到右下角每一步允许左、右、上、下移动需求描述里写着“有向无环图中的最短路径”。我盯着这行字愣了一下只要允许四个方向移动每个格子和邻居之间就是双向边双向边本身就构成一个长度为2的环这图怎么可能无环后来我把这个问题彻底捋了一遍才发现这个标题里其实藏着一个值得掰开揉碎讲清楚的点什么情况下“四方向移动”可以被当作“有向无环图”来处理什么情况下不能。这篇文章就把这个矛盾拆开给你讲明白从建模、算法原理、代码实现到踩坑避雷的完整思路顺带把DAG最短路径和通用最短路径算法的适用边界也理清楚。适合看这篇文章的人有三类准备算法面试、正在刷网格类题目的同学实际业务里做地图寻路、格子地图路径规划但不想依赖现成引擎的开发者以及刚接触DAG动规、总被“有环还是无环”绕晕的新手。1. 先说结论这个标题里藏着一个矛盾1.1 “四方向移动”和“有向无环图”天然打架先把图模型说清楚。网格去掉障碍后每个格子是一个顶点相邻格子之间存在一条有向边方向是“能从A走到B”。四个方向移动意味着每一条相邻关系都是双向的能从(i,j)走到(i,j1)也一定能从(i,j1)走回(i,j)。于是(i,j) - (i,j1) - (i,j)就是一个环长度为2。同理上/下之间也有环。所以只要题目允许四个方向整张图就一定包含环它不可能是严格意义上的有向无环图。那为什么很多人一看到“最短路径”就条件反射要写拓扑排序DP因为教科书里的DAG最短路径问题是这么写的图无环按拓扑序逐一松弛O(VE)搞定比Dijkstra还快。但教科书没有告诉你这个前提是你手里的图真的是DAG。如果你把四方向网格硬塞给拓扑排序要么排序失败要么根本没有环可排算法直接歇菜。我见过不少新手在这个地方栽跟头看到“最短路径”四个字立刻打开一个二维dist数组开始按某种顺序滚动更新。但四方向网格的更新是相互依赖的不存在天然的“先后关系”直接滚动更新很容易算出一个错误答案或者陷入无限循环。这个“有环还是无环”的判断是整个问题的第一个分水岭。1.2 什么情况下“四方向”也能归约成DAG不过这件事反过来想有点意思。如果网格是完整的、没有障碍、所有边权非负起点在左上角、终点在右下角那么四方向移动的最优路径其实永远不会用到“向左”和“向上”。用反证法来看。假设一段最优路径里出现了向左的一步从(i,j)走到(i,j-1)。因为终点在起点右下角行坐标和列坐标都比起点大所以之后必然还要从第j-1列回到第j列或更右的列。这一来一回中间夹着的部分构成一个环。把环删掉剩下的仍然是从起点到终点的一条合法路径而且由于每步成本非负删掉环之后总成本不会增加。向上移动也是同理。重复删除所有向左、向上的环最后得到一条只向右、只向下的路径成本不高于原最优路径。所以在“完整网格 非负边权 左上到右下”这三个条件下四方向问题的最优解一定存在于“向右/向下”这个DAG里。这个归约非常关键原始网格虽然整体有环但最优解落在其中一个特殊的DAG子图上这就是题目敢写“有向无环图中的最短路径”的原因。当然一旦条件不满足比如网格里有障碍、起点终点位置不满足左上到右下、边权存在负值这个归约就不成立了。这时候必须老老实实用通用最短路算法不能盲目套DAG DP。1.3 这篇文章的处理路线我打算用两种算法把这类“最低成本路径”完整串一遍。第一种是在真正的DAG上跑拓扑序DP对应“向右/向下”或任何有拓扑序的网格第二种是完整四方向移动时的Dijkstra这是最常用也最稳的方案不需要图无环只要边权非负。然后我会专门讲障碍、负权、限步数三种衍生场景怎么建模。最后是实际踩坑记录和性能对比。我自己的习惯是拿到这类问题先花两分钟回答三个问题图到底有没有环边权是不是非负状态空间能不能压缩三个问题回答完用哪个算法、怎么写状态、复杂度能压到多少基本就定下来了。这篇文章也会按照这个思路来展开。2. 网格最短路径的建模与核心思路2.1 把网格变成图的三个口径问题动手写代码前先把建模口径定清楚否则后面全是坑。第一个问题是节点怎么表示。最直观的方式是用二维坐标(i,j)在Python里直接用二元组传给堆写起来最方便。但如果你要压性能或者代码里频繁做坐标转换把它压成一维索引更划算idx i * cols j这样dist和visited都可以用一维数组缓存友好堆里也只需要存一个整数。我的建议是规模小无所谓规模一旦超过500×500优先用一维索引。第二个问题是成本算在哪个环节。网格寻路里常见的口径有两种一种是“进入一个格子才产生成本”另一种是“离开一个格子产生成本”。二者的总成本对比会有细微差别。我自己习惯用第一种口径起点成本单独处理其余每个格子只在进入时累加。对应到代码里起点dist设成0扩展到邻居时nd d grid[nr][nc]如果题目要求起点成本也算那初始dist就直接设成grid[0][0]。这个口径一致性直接影响答案后面章节我还会再提一次。第三个问题是“边权”到底是什么。如果边权等于目标格成本结论是最低成本路径如果边权恒等于1结论就退化成最短步数这时候其实BFS就够了不需要Dijkstra更不需要DP。很多人在带权网格上写BFS是因为把“最低成本”和“最少步数”搞混了。搞清楚这三个口径后面的代码才有意义。2.2 DAG上的最短路径为什么快拓扑序DP原理先复习一下DAG最短路径的核心公式。对于一条边(u, v)松弛操作是dist[v] min(dist[v], dist[u] w(u,v))在DAG上做最短路最大的便利是一个拓扑序。只要所有边都从拓扑序靠前的节点指向靠后的节点那么按拓扑序从头到尾扫一遍当处理到某个节点v时所有能到达v的节点都已经完成了松弛计算因此v的dist在这一刻就是最终值不需要回头再更新。这就解决了普通DP在网格上“先算谁、后算谁”的难题。右/下网格天然满足这个条件从(i,j)只能走向(i1,j)或(i,j1)而行加列这个值严格递增。所以只要按行优先顺序遍历每个节点被处理时它上方和左方的节点一定都算完了DP就能一次通过。复杂度只有O(VE)连堆都不需要这是它比Dijkstra快的原因。对比DijkstraDijkstra每轮都要从优先队列里取当前dist最小的点因为图里有环某个节点的最短距离可能在后期才被更短的路径刷新所以需要反复比较和更新。DAG DP把这一整套复杂机制简化成了“按序结算一次”常数极小实现也简单。2.3 核心洞察非负成本下四方向如何被“折”成两方向前面那一节我用反证法说明了“最优路径不会向左或向上”这里再深化一下它到底给解题带来什么实际好处。第一个好处是维度缩减。四方向问题是二维的、有环的很多通用算法要处理大量无效搜索而单调路径问题的状态天然有序只需要一个双重循环。这在实际工程里可能意味着性能从几秒降到几毫秒。第二个好处是它给了你一个“正确性自检”的锚点。当你用完整的四方向Dijkstra在完整网格上跑出一个答案又用右下DP跑出另一个答案而两份答案不一致时不要急着怀疑某一个算法——先检查你的网格是不是真的“完整”某个格子是不是不小心被当成障碍了边权是不是出现负值了起点终点是不是不在约定的位置大多数情况下答案不一致意味着建模口径出了问题。第三个好处是它能在面试或方案评审时帮你把思路讲清楚。我经常在评审里听到这样的表述“这个图虽然看起来有环但因为成本非负最优路径不会走回头路所以可以等价为单调路径。”这句话一说出来对方就知道你理解了问题的本质而不只是会背模板。3. 实操从拓扑排序DP到Dijkstra完整实现3.1 方案A只允许右/下时的拓扑排序DP先上最直接的版本。假设题目要求你从(0,0)走到(rows-1, cols-1)每一步只能向右或向下格子成本给你一个二维数组grid进入一个格子计费起点成本不算也就是dist[0][0] 0。def min_cost_right_down(grid): if not grid or not grid[0]:
