在算法面试和工程实战里多段图的最短路径这个概念很少被直接喊出来但它其实藏在各种分段决策问题的底层。动态规划的多段图最短路径解法是我认为最适合用来理解“状态设计”这个抽象概念的入门案例很多看起来完全不同的需求——货物多级转运的路线选择、项目排期中寻找代价最小的任务链路、自动化流程里规划穿越多个处理环节的路径——都能落到同一个模型上。这篇文章我会从一个完整算例出发把多段图最短路径的前向、后向两种动态规划思路、可落地的Python代码以及常见变形一次讲透。不管是准备算法面试还是被业务里的分段最优化问题缠住照这个思路都能少走弯路。1. 多段图到底是什么以及为什么不能“一把梭跑Dijkstra”1.1 多段图的定义与直觉理解先说标准定义。给定一个有向带权图顶点集被划分成 k 个互不相交的子集V1、V2……Vk其中 V1 里只有源点Vk 里只有汇点。任意一条边都从第 p 段的某个顶点出发指向第 p1 段的某个顶点不允许同段内部连边也不允许跳段。目标是从源点出发沿着边一格一格往后走最终到达汇点累计边权和最小。因为没有回头路所以这必然是一条经过 k 个阶段、恰好从每个段里选出一个顶点的路径。直觉上可以把它理解成一条流水线。每个阶段是一个工位工位里摆着几台可选的机器上一台机器的输出送进下一台某台机器的输入每转移一次都要付一次成本最后把整条流水线的总成本压到最低。这个模型在物流、排程、路径规划里特别常见只不过现实场景不会直接告诉你“这是多段图”需要自己去把阶段边界识别出来。需要注意一点多段图没有环。边永远从低段指向高段所以它是一个天然有序的有向无环图。这一点是后面所有动态规划推倒过程能够成立的基础。很多教材把“边只允许连接相邻两段”作为默认条件但实际工程里偶尔会出现跨段边此时仍然可以靠拓扑序做DP只是不能再用“逐段填表”这个简化假设。1.2 为什么暴力枚举和贪心都靠不住拿到这个问题的第一反应往往是从源点到汇点把所有路径枚举一遍。假设每段平均有 m 个顶点一共 k 段路径总数大约是 m 的 k 次方。这个数字涨得有多快我举个例子你就感受到了每段只有 10 个点、一共 10 段路径数是 100 亿级别现代计算机想全部枚举完也吃不消。工程上稍微遇到大一点的图暴力法基本出局。那贪心呢既然每段必须选一个顶点能不能每走到一个顶点就选当前出边里权值最小的那条看着挺合理但局部最优拼不出全局最优。我用后面完整算例里的数据提前剧透一下从源点出发每一步都挑最小出边最终会走出一条总代价 16 的路径可真实最优解只有 13。贪心的问题在于它不知道当前省下的那点成本会在后面的环节用更大的代价补回来。动态规划之所以能解决这个问题靠的是两个性质最优子结构和无后效性。从源点到汇点的最短路径里任何一个中间顶点到汇点的子路径也必然是从该顶点到汇点的最短路径而当前顶点一旦确定前面是怎么走到这里的对后续决策没有任何影响。这两个性质一满足就可以放心地把大规模问题拆成小规模问题用一张表逐段填出来。2. 从汇点倒推设计状态后向动态规划的公式与手算全过程2.1 状态定义与递推公式后向动态规划的核心状态是 cost[i]表示从顶点 i 出发、沿着后续各段走到汇点所需的最短路径长度。因为图没有环所以汇点就是天然边界cost[汇点] 0。对于任意非汇点的顶点 i假设它下一段能到达的候选顶点为 j1、j2……那么cost[i] min( w(i, j1) cost[j1], w(i, j2) cost[j2], …… )其中 w(i, j) 是边 i→j 的权值。这个公式的本质是站在顶点 i 上先把所有可能的后继顶点到汇点的最优值都拿在手里然后比较“走哪条出边 后继的最优值”最小就选哪条。填表顺序必须从汇点所在段开始逐段向前。因为只有先算出所有下一段顶点的 cost当前顶点的转移才有据可依。为什么把状态定义成“从当前点到汇点”而不是“从源点到当前点”两者都能解但从汇点倒推的写法更贴近“子问题”的自然划分每个顶点都代表一个独立的决策点后面的事情全部封装在 cost 里做选择时只需要看当前一步和后继的最优值。这会让转移方程非常干净。2.2 一个6段算例的手算过程纸上谈兵不如拿真实算例推一遍。我设计一个 6 段共 13 个顶点的图顶点编号从 1 到 13源点是 1汇点是 13。各段划分如下第 1 段顶点 1第 2 段顶点 2、3、4第 3 段顶点 5、6、7第 4 段顶点 8、9、10第 5 段顶点 11、12第 6 段顶点 13边权我列出来方便你跟着复算起点终点与权值12(5), 3(3), 4(6)25(2), 6(4), 7(7)35(6), 6(2), 7(3)45(8), 6(5), 7(4)58(3), 9(4), 10(6)68(9), 9(7), 10(5)78(4), 9(2), 10(1)811(3), 12(5)911(6), 12(3)1011(4), 12(2)1113(3)1213(4)先初始化边界cost[13] 0。接着看第 5 段cost[11] 3 cost[13] 3cost[12] 4 cost[13] 4第 4 段就稍微需要比一比了cost[8] min( 336, 549 ) 6选 11cost[9] min( 639, 347 ) 7选 12cost[10] min( 437, 246 ) 6选 12第 3 段cost[5] min( 369, 4711, 6612 ) 9选 8cost[6] min( 9615, 7714, 5611 ) 11选 10cost[7] min( 4610, 279, 167 ) 7选 10第 2 段cost[2] min( 2911, 41115, 7714 ) 11选 5cost[3] min( 6915, 21113, 3710 ) 10选 7cost[4] min( 8917, 51116, 4711 ) 11选 7最后是源点cost[1] min( 51116, 31013, 61117 ) 13选 3最终最短路径长度为 13。整张表的计算结果如下顶点cost[i]选择的后继130-1131312413861197121061259861110771021153107411711332.3 从cost表回溯完整路径只有长度还不够业务里通常要把整条路径输出出来。做法很简单在填表的时候每个顶点记下“让我得到最小 cost 的那个后继顶点”最后从源点开始一路沿着后继往下跳。按上面算例源点 1 指向 33 指向 77 指向 1010 指向 1212 指向 13所以最短路径是1 → 3 → 7 → 10 → 12 → 13验证一下边权3 3 1 2 4 13和 cost[1] 完全一致。这种回溯方式需要额外一个数组存后继关系空间开销是 O(n)非常小。很多人习惯在 DP 表里只存数值等到真正要用结果时发现路径回溯不了只能重算一遍这就亏了建议一开始就把选择记录下来。3. 从源点正推的镜像解法前向递推与等价性分析3.1 前向递推的状态与公式后向 DP 是从终点往起点看前向 DP 则是从起点往终点推。核心状态改成 dist[i]表示从源点到顶点 i 的最短路径长度。边界条件是 dist[源点] 0。递推公式dist[i] min( dist[j] w(j, i) )这里的 j 遍历所有可以到达 i 的上一段顶点。填表顺序完全反过来从第 1 段开始逐段向后扫算顶点 i 的时候所有可能前驱顶点的 dist 值都已经确定。还是用同一个算例跑一遍前向过程。初始化 dist[1] 0第 2 段dist[2] 5dist[3] 3dist[4] 6第 3 段dist[5] min( 527, 369, 6814 ) 7前驱选 2dist[6] min( 549, 325, 6511 ) 5前驱选 3dist[7] min( 5712, 336, 6410 ) 6前驱选 3第 4 段dist[8] min( 7310, 5914, 6410 ) 10前驱选 5 或 7dist[9] min( 7411, 5712, 628 ) 8前驱选 7dist[10] min( 7613, 5510, 617 ) 7前驱选 7第 5 段dist[11] min( 10313, 8614, 7411 ) 11前驱选 10dist[12] min( 10515, 8311, 729 ) 9前驱选 10第 6 段dist[13] min( 11314, 9413 ) 13前驱选 12最终长度同样是 13。回溯13 的前驱是 1212 的前驱是 1010 的前驱是 77 的前驱是 33 的前驱是 1路径同样是 1 → 3 → 7 → 10 → 12 → 13。3.2 正推与倒推的等价性和选择两种方向在数学上是完全等价的因为它们都建立在同一个最优子结构上。后向公式把问题看成“从当前点到终点”前向公式把它看成“从起点到当前点”本质上是一个硬币的两面。你甚至可以在一张图上同时用两个方向算一遍拿结果互相校验这是非常有效的调试手段。工程里怎么选主要看你的数据组织方式。如果图用邻接表存了每个顶点的出边那后向 DP 写起来最顺手从汇点往前扫直接遍历出边即可。如果图本身给你的是前驱关系或者业务里更习惯从起点开始逐层推进那就用前向 DP。另外当“终点”的动态性更强时比如终点会根据前序决策变化前向往往更自然当“起点”的选择会影响全局时后向通常更方便兜底。有一点要提醒正推和倒推最终长度一定相等但回溯出来的路径也必须一致。如果你算出来长度一样、路径却不同说明你的状态定义或者转移条件里有隐藏 bug比如漏考虑了一条边或者 INF 初始值参与过运算。这种情况在调试初期很常见值得多留一个心眼。4. 能直接搬到工程里的实现Python代码与边界条件4.1 基于邻接表的自底向上实现前面手算过程其实就是算法的完整步骤代码只是把大脑的运算翻译成循环。我建议用邻接表组织图每个顶点列出全部出边。以下是后向 DP 的 Python 参考实现顶点编号为 0 到 n-1源点是 0汇点是 n-1from math import inf def multi_stage_shortest_path(n, graph): graph[v] [(to, w), ...] 表示从 v 到 to 的边权为 w 默认顶点编号按源点到汇点严格递增汇点是最大编号 cost [inf] * n parent [-1] * n cost[n - 1] 0 for v in range(n - 2, -1, -1): for to, w in graph[v]: candidate w cost[to] if candidate cost[v]: cost[v] candidate parent[v] to if cost[0] inf: return inf, [] path [] cur 0 while cur ! -1: path.append(cur) cur parent[cur] return cost[0], path如果希望代码更贴合“多段”这个概念可以用段边界数组分批处理。比如 segments 数组存的是每一段起始顶点的编号从第倒数第二段开始倒着处理逻辑会更清晰def multi_stage_by_segment(n, graph, segments): # segments[s] 表示第 s 段第一个顶点的编号最后一段只有一个汇点 cost [inf] * n parent [-1] * n cost[n - 1] 0 for s in range(len(segments) - 2, -1, -1): seg_start segments[s] seg_end segments[s 1] # 下一段起点同时是当前段的末尾哨兵 for v in range(seg_start, seg_end): for to, w in graph[v]: if w cost[to] cost[v]: cost[v] w cost[to] parent[v] to return cost[0], reconstruct(0, parent)这两种实现的时间复杂度都是 O(ne)每个顶点和每条边最多被访问一次。空间复杂度是 O(ne)其中 O(e) 用来存邻接表另外两个 O(n) 数组存 cost 和 parent。4.2 复杂度对比与初始化陷阱不同方案的成本差距非常大。暴力枚举是 O(m^k)指数增长约等于不可用通用 Dijkstra 用优先队列是 O((ne) log n)正确但是杀鸡用牛刀多段图 DP 利用分段结构做到 O(ne)连优先队列的堆操作都省了是这类图上的最优选择之一。初始化最值得小心的是 INF 的选择。经典多段图里权值可能为负如果 INF 取一个固定的大整数比如 10^18而负权又足够大可能出现“INF 加了一个负数后反而变小”的假象导致不存在的边被当成候选。稳妥做法有两种要么在转移前显式判断 cost[to] ! INF要么在语言允许时直接用 float(inf)。Python 里 inf 加任何有限数仍然是 inf天然免疫这个问题。其他语言里没有无限大时就选一个超过所有可能的路径总权值上限的大数再配合显式判断。另一个容易被忽略的是顶点编号顺序。后向 DP 的循环方式隐含了一个前提任意一条边的起点编号都小于终点编号。多段图定义里天然满足这一点但工程数据从接口传进来时未必规整。接数据后先做一个校验或者自己先做一次拓扑排序能省去后面大量怪问题。4.3 工程实现中容易踩的坑第一个坑是只算长度不回溯路径。等业务方需要具体路线时parent 数组没存只能重新再跑一遍。第二个坑是把 parent 数组含义搞混后向 DP 里存的是“我下一步去哪”前向 DP 里存的是“我是从哪来的”回溯循环的方向完全相反代码写混了会得到一条断掉的路径。第三个坑出现在图不连通时。某个顶点没有出边它的 cost 就会一直保持 INF如果源点到汇点本来就不连通最终 cost[0] 也是 INF。代码里如果不检查就直接用会把 inf 当普通数字参与业务计算结果就是线上出现莫名其妙的溢出或者超时。我的习惯是函数出口统一判断一次cost[0] 等于 INF 就返回空路径。最后一个坑是循环顺序。曾经有人为了优化把内层循环改成遍历所有边而不是遍历当前顶点的出边结果引入了大量冗余计算复杂度直接退化到 O(n * e)还把状态污染了。多段图的结构足够简单老老实实“按段倒序 按顶点出边”就是最高效写法不要过度设计。5. 多段图在真实问题中的变形与扩展5.1 从最短到最长关键路径案例把求最短改成求最长就是项目管理里著名的关键路径问题。每个顶点代表一个任务节点边权代表任务耗时从项目启动到项目交付中间有很多条并行路径其中耗时最长的路径决定了整个项目的最短完成时间这条路径就叫关键路径。代码层面的调整小到可以忽略后向递推公式里的 min 改成 maxcost 初始化从 0 改成负无穷即可。工程上更常见的做法是直接把所有边权取相反数再跑一遍最短路径 DP。不过要注意如果图里存在负权回环这个取反技巧就不安全了但多段图天然无环所以可以放心。5.2 必经点和非相邻段的约束现实问题经常多加一条要求路径必须经过某个指定的顶点。处理思路是把原图从必经点处拆开分成前半个多段图和后半个多段图分别求出源点到必经点、必经点到汇点的最优值再加起来。如果必经点有多个且相互之间存在先后顺序就得按顺序切成多段求解不能简单叠加。还有一种情况是数据里出现了跨段边比如从第 2 段直接连到第 4 段。严格定义下这已经不是多段图但只要边仍然是从小编号指向大编号整张图就是一个拓扑有序的 DAG直接套用拓扑序 DP 就可以。处理时把“逐段倒序循环”改成“全局编号倒序循环”逻辑依然成立代价是你不能再依赖段边界做批量扫描。5.3 多段图DP与其他经典DP的关系学完多段图再看其他动态规划会感觉一通百通。比如编辑距离可以看成在两个字符串之间逐字符做匹配、插入、删除的阶段性决策背包问题则是按物品一件件处理每个物品拿还是不拿就是一个阶段的二选一。它们共同的内核都是定义状态、写出转移方程、确定填表顺序、保证无后效性。区别在于多段图把“阶段”这个维度显式画了出来每个阶段只能往下一阶段走所以状态顺序天然固定。像这种“我会不会做”的问题难点根本不在转移方程而在识别“这是不是多段图结构”以及“状态应该定义成什么”。见过足够多的例子之后这种识别能力会越来越快。6. 我在实际编码时用到的三条检查口诀6.1 先画段边界再写循环拿到问题不要急着敲代码。我的习惯是先找纸笔把每一段包含哪些顶点画出来标注源点、汇点和段边界。确定边界之后再去看数据里给的边是否真的都在相邻段之间如果有跨段边立刻调整建模方式。这个动作看起来笨但能避免 80% 的代码返工。尤其当你面对的是别人传来的图数据字段名不直观乱得很先画结构图比直接读字段高效得多。6.2 验证路径而不是只验证长度只在最后输出一个最短长度隐患很大。长度是对的不代表路径选择是对的因为可能存在多条等长路径你的 DP 选了其中一条但那条路径的中间边权加和时有 bug。我在自己做测试时一定会把路径顶点列表打出来再人工加一遍边权确认等于 DP 输出的 cost。能输出正确路径又能对上长度这个实现才基本可信。6.3 随机小图对照暴力枚举最有效的自测工具是暴力破解它代码简单、逻辑直接适合当基准答案。你可以写一个随机生成小规模多段图的函数用枚举法求出正确路径再和 DP 版本的结果对比。随机跑几百组如果完全一致实现的正确性就有保障了。这个技巧不局限于多段图几乎所有 DP 题都能用同样的方法验证。最后说一点个人体会多段图最短路径是少数“手算一遍之后实现起来几乎不会错”的DP题目。核心不在于代码而在于你能不能把手算时那种“沿着段倒推、每个点取最小”的思考过程原封不动翻译成循环和数组。把上面这个6段算例自己推一遍再对照代码跑一遍比看十遍理论都管用。如果正推和倒推两条路算出来的路径不一致那恭喜你一次很不错的调试训练已经在等你了。