前阵子接到一个需求，要在网格上找一个最低成本路径，从左上角到右下角，每一步允许左、右、上、下移动，需求描述里写着“有向无环图中的最短路径”。我盯着这行字愣了一下：只要允许四个方向移动，每个格子和邻居之间就是双向边，双向边本身就构成一个长度为2的环，这图怎么可能无环？
后来我把这个问题彻底捋了一遍，才发现这个标题里其实藏着一个值得掰开揉碎讲清楚的点：什么情况下“四方向移动”可以被当作“有向无环图”来处理，什么情况下不能。这篇文章就把这个矛盾拆开，给你讲明白从建模、算法原理、代码实现到踩坑避雷的完整思路，顺带把DAG最短路径和通用最短路径算法的适用边界也理清楚。
适合看这篇文章的人有三类：准备算法面试、正在刷网格类题目的同学；实际业务里做地图寻路、格子地图路径规划但不想依赖现成引擎的开发者；以及刚接触DAG动规、总被“有环还是无环”绕晕的新手。
1. 先说结论：这个标题里藏着一个矛盾
1.1 “四方向移动”和“有向无环图”天然打架
先把图模型说清楚。网格去掉障碍后，每个格子是一个顶点，相邻格子之间存在一条有向边，方向是“能从A走到B”。四个方向移动意味着每一条相邻关系都是双向的：能从(i,j)走到(i,j+1)，也一定能从(i,j+1)走回(i,j)。于是(i,j) -> (i,j+1) -> (i,j)就是一个环，长度为2。同理，上/下之间也有环。所以只要题目允许四个方向，整张图就一定包含环，它不可能是严格意义上的有向无环图。
那为什么很多人一看到“最短路径”就条件反射要写拓扑排序DP？因为教科书里的DAG最短路径问题是这么写的：图无环，按拓扑序逐一松弛，O(V+E)搞定，比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)只能走向(i+1,j)或(i,j+1)，而行加列这个值严格递增。所以只要按行优先顺序遍历，每个节点被处理时，它上方和左方的节点一定都算完了，DP就能一次通过。复杂度只有O(V+E)，连堆都不需要，这是它比Dijkstra快的原因。
对比Dijkstra：Dijkstra每轮都要从优先队列里取当前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]:
)
