企业官网建设流程全解析

提到动态规划，很多人的第一反应是背包问题，或者斐波那契数列的备忘录写法。但在实际工程和算法竞赛里，有一个非常适合入门、又极度实用的模型，它就是多段图的最短路径问题。多段图（multistage graph）是一种天然分层的图结构，顶点被划分成若干连续的段，边只会从前面的一段指向后面的一段，我们要做的是在源点到汇点的海量候选路径中，找到总权值最小的一条，也就是最短路径。这篇文章我会从场景、状态设计、推导、代码实现到排查技巧，完整走一遍，相信看完你不仅能看懂，还能直接拿去教别人。

1. 多段图最短路径要解决什么问题

1.1 多段图的结构定义

先给一个不绕弯子的定义。一个多段图是有向图 G = (V, E)，顶点被切分成 k 个集合，也就是 k 段，段之间有严格的次序关系。源点在第 0 段，汇点在第 k-1 段，每条边 (u, v) 都满足 u 所在的段号严格小于 v 所在的段号。注意是严格小于，不能在同一段内连边，也不允许往后跳多段以外的方向回头走。

这种结构在数学上叫"分层有向无环图"，它是 DAG（有向无环图）的一种特例。DAG 本身就是动态规划最舒服的舞台，而多段图把"拓扑序"直接钦定成了段号，等于把顺序喂到你嘴边。常见的形式是相邻段之间全连接，但工程上更普遍的是稀疏连接：某些顶点之间没有边，因为现实约束本来就不允许某些选择组合。

初学者容易混淆的一点是：多段图不一定要求每一段都非空，也不要求段之间只在相邻段连边。实际资料里有时会出现"跨段边"，比如第 1 段的节点直接指向第 3 段，这在严格定义里不算标准多段图，但处理方法完全一样，后面我会专门讲这个坑。

1.2 背后的一类真实场景

如果只看定义，会觉得这是个纯学术玩具。但实际上，多段图最短路径是很多决策问题的抽象骨架，理解它之后，很多看着复杂的问题其实就是换了一层皮。

第一个典型场景是项目排期。一个软件项目从需求分析、概要设计、编码到测试，每个阶段可能在好几个候选方案里选一个，不同方案的成本不同，而前一阶段的某个方案会影响后一阶段某些方案的成本。你希望总成本最低，这就是一个标准的多段图最短路径：阶段是段，方案是顶点，候选跳转是边，成本是权值。

第二个场景是通信网络的路径选择。某些专用网络被划分成多个自治域或骨干层，报文从源节点到目的节点必须逐域转发，每个域内可以选不同的入口和出口节点，域间链路的代价就是边权。你要求端到端总代价最小，本质上就是多段图问题。

第三个场景更生活化一点：制造业的批次生产计划。原材料采购、零部件加工、总装、质检每一环都有可选供应商或工艺路线，后续环节受前面选择影响，单价不同，多段图直接对应"从原料到成品的最小总成本路径"。

这些场景的共同特征是有明确的阶段顺序，每个阶段的选择只依赖当前状态而不依赖更早的历史。一句话：凡是"分阶段做决策、每阶段选一个动作、代价可叠加"的优化问题，都可以先往多段图上套一套，这也是动态规划里最值钱的一种迁移能力。

2. 为什么这道题是理解动态规划的绝佳入口

2.1 枚举式解法先算一笔账

先看看暴力枚举要付出什么代价。假设图一共有 k 段，中间第 i 段有 n_i 个顶点，那么从源点到汇点的完整路径数量大约等于 n_1 × n_2 × … × n_{k-2}。这个乘积是典型的指数增长。

我给你算个具体的数。假设共 6 段，中间 4 段每段 10 个顶点，全连接的情况下候选路径有 10^4 = 10000 条。每条路径长度是 5 次加法，那么暴力枚举要做约 50000 次加法，这看着还好。但每段增加到 100 个顶点呢？路径数量是 100^4 = 1 亿。这里还没有算上每次比较和路径记录的额外开销，数据规模稍微涨一点，枚举直接不可行。

指数增长最可怕的地方是它不像多项式那样"慢一点"，而是直接跨过一个量级后让你没法算。很多新手觉得"我机器快，枚举也能跑"，但那只是没碰到大一点的图。真实工程里一张图几百上千个顶点是常态，枚举绝对撑不住。

2.2 动态规划成立的两个条件

动态规划之所以能在这里发力，是因为这个问题满足两个本质条件。第一个是最优子结构：从源点到汇点的最短路径，如果它经过某个中间顶点 x，那么从 x 到汇点的这一段，必须是从 x 到汇点最短的路径。否则你就可以把这一段替换成更短的路，得到一条整体更短的路，矛盾。

用大白话说：全局最优解砍掉一截之后，剩下的那截仍然是子问题的最优解。这条性质保证了我们可以"分段下结论"，把大问题拆成小问题逐个击破。

第二个条件是重叠子问题：不同的完整路径会大量共享中间部分。比如从源点出发的所有路径，都会经过第 2 段的某些顶点，而从这些顶点到汇点的最短路径只需要算一次，后续所有经过它们的候选路径都能直接复用这个结果。

注意这两个条件和"无后效性"是同一个意思：从第 i 段顶点出发的最优路径，只取决于该顶点本身，不取决于之前是怎么走到这个顶点的。多段图天然满足这一条，因为边只向前延伸，未来的代价和过去的历史没有关联。

2.3 前向与后向：两个递推方向

多段图上做动态规划有两种方向，很多教材都提到但往往讲得含糊，我拆开说清楚。

后向法（backward，也叫反向递推）是从汇点往源点算。定义 cost[v] 为"从顶点 v 出发到汇点的最短路径长度"。先给汇点的 cost 赋 0，然后从倒数第二段开始往前逐段处理，每个顶点的 cost 由它所有出边指向的、后一段顶点的 cost 加上边权取最小得到。最终 cost[source] 就是答案。

前向法（forward，也叫正向递推）是从源点往汇点算。定义 cost[v] 为"从源点到顶点 v 的最短路径长度"。先给源点赋 0，然后从第二段开始往后逐段处理，每个顶点的 cost 由它所有入边来源的、前一段顶点的 cost 加上边权取最小得到。最终 cost[sink] 就是答案。

两种方法在数学上完全等价，代码差异只是"看入边还是看出边"。我个人建议入门时先苦练后向法，因为后向法在推演最小化问题时更贴合"从终点倒推"的直觉，而且它需要的反向邻接表都不用在多段图上单独建。不过前向法在某些变体里更方便，比如处理多个源点时，后向法要加超级汇点，前向法要加超级源点。

3. 状态定义与转移方程：一个公式贯穿全程

3.1 状态设计：cost[v] 的含义

状态设计是整个动态规划的灵魂。这里的状态不复杂，就是一句话：cost[v] 表示从顶点 v 到汇点的最短路径长度。如果你用前向法，就是 cost[v] 表示从源点到顶点 v 的最短路径长度。

我见过很多新手卡在这里，不是因为公式多看不懂，而是不确定"状态到底存哪个量"。有一条判断标准很好用：问你最后想要什么。最后要的是源点到汇点的最短路径长度，那我倒推，站在某个中间顶点 v 的角度问"从 v 到终点最短还有多远"，这个距离只和 v 有关，和前面的选择无关，这就是一个合格的状态。

如果你还想把路径本身也拿出来，光存 cost 不够，得额外存一个决策数组。比如 next[v] 记录从 v 出发走最短路径时，下一步应该去哪个顶点。这样算完之后从源点沿着 next 一路跳到汇点，路径就出来了。这个技巧在多段图以外的很多 DP 问题里同样适用，属于提前布局。

3.2 转移方程推导与证明

既然 cost[v] 是从 v 到汇点的最短距离，那站在 v 上，下一步只能走它的某一条出边 (v, u)。一旦选了 u，后续的代价就变成"从 u 到汇点的最短距离"，也就是 cost[u]。所以 v 的最短距离应该是所有出边里"w(v, u) + cost[u]"最小的那个。

写成公式就是：

cost[v] = min{ w(v, u) + cost[u] | (v, u) ∈ E }

这个方程就是多段图最短路径的全部核心。它的正确性证明用反证法：如果存在一条从 v 到汇点的路径比公式计算的结果更短，设它经过的第一个后继节点是 u'，那么从 u' 到汇点的那段路径一定比 cost[u'] 更短，这和我们假设 cost[u'] 是最短距离矛盾。

这里我特别想强调一点：很多人看公式觉得简单，但实际操作时容易忽略推导方向。后向法是从后往前：处理第 i 段顶点时，第 i+1 段的 cost 必须已经算完。因为多段图的边只会指向更大的段号，所以只要严格按照段号从大到小逐段处理，依赖顺序就天然满足，不需要再做拓扑排序。

3.3 边界条件与初始化细节

边界条件是最容易被忽略、也最容易出错的地方，我单独拎出来说。

第一个边界是汇点。汇点没有出边，它到自己的最短距离是 0，所以 cost[sink] = 0。这个初始化必须在开始递推前就设好，否则递推系列里的"终点"没有初值，整个链条断裂。

第二个边界是源点。后向法里源点没有特殊情况，只是个普通中间节点；前向法里则是 cost[source] = 0 作为启动值。

第三个边界是"不可达"的处理。如果某个顶点的出边全部指向尚未计算的顶点，或者根本没有出边（除了汇点），它的 cost 应该保持无穷大。不，更严格说，多段图里除了汇点每个顶点至少有一条出边，不然这个顶点本身就是死路，不影响全图最优解，但会影响路径回溯时的一致性判断。实现时建议用 float('inf') 表示不可达，最后判断 cost[source] 是否为 inf，如果是，说明源点到汇点根本不连通，输出"无路径"而不是返回一个错乱的大数。

4. 完整实现：从建图、求解到路径回溯

4.1 图的数据结构与建图

多段图的实现第一步是选对数据结构。最常见的做法是邻接表：用一个字典 graph，graph[u] 是列表，元素是 (v, w) 这样的元组，表示从 u 到 v 有一条权值为 w 的边。这样做的原因是多段图往往是稀疏的，用邻接矩阵 O(V^2) 的空间在几百个顶点时还好，顶点上千之后就开始浪费了，邻接表更贴合实际。

同时还要保存每个顶点属于哪个段，我用一个字典 stages，键是顶点编号，值是段号。有了这两个结构，所有后续逻辑都很好写。

这里有一个实操建议：如果题目是用二维数组给你的，第一件事把它转成邻接表，而不是直接在数组上写 DP。二维数组在输入阶段看着直观，但递推过程中反复扫描整行做最小值筛选，代码冗长还容易把行列下标写反，转成邻接表之后逻辑清晰很多，排查也方便。

# 示例：构造下面的多段图 # 段0:{0} 段1:{1,2,3} 段2:{4,5,6} 段3:{7,8} 段4:{9} graph = { 0: [(1, 1), (2, 2), (3, 5)], 1: [(4, 4), (5, 11)], 2: [(4, 9), (5, 5), (6, 16)], 3: [(5, 6), (6, 13)], 4: [(7, 18), (8, 2)], 5: [(7, 10), (8, 5)], 6: [(7, 2), (8, 11)], 7: [(9, 16)], 8: [(9, 4)], 9: [] } stages = {0: 0, 1: 1, 2: 1, 3: 1, 4: 2, 5: 2, 6: 2, 7: 3, 8: 3, 9: 4}

4.2 后向递推求解代码

有了图之后，核心求解代码很短。我写的这个版本会同时输出最短路径长度和完整路径，核心逻辑就是把转移方程翻译成循环：

def multistage_dp_backward(graph, stages, source, sink): # 初始化 cost = {sink: 0} nxt = {sink: None} # 按顶点所在的段号排序，从大到小处理 max_stage = max(stages.values()) nodes_by_stage = {} for node, stage in stages.items(): nodes_by_stage.setdefault(stage, []).append(node) for stage in range(max_stage - 1, -1, -1): for u in nodes_by_stage.get(stage, []): if u == sink: continue best_cost = float('inf') best_next = None for v, w in graph.get(u, []): if v not in cost: # 理论上多段图不会出现这种情况，但跨段边会导致此分支 continue total = w + cost[v] if total < best_cost: best_cost = total best_next = v cost[u] = best_cost nxt[u] = best_next # 路径回溯 path = [] cur = source while cur is not None: path.append(cur) cur = nxt.get(cur) if cost[source] == float('inf'): return None, [] return cost[source], path

这段代码有四个关键点值得展开。

第一，为什么按段号从大到小循环？因为后向法的转移方程依赖"后一段的 cost 已经算好"，段号从大到小能保证这一点。这里其实是把 DAG 的拓扑排序简化成了"按段号排序"，适用性强且不用额外建拓扑序列。

第二，为什么用字典存 cost 而不是数组？多段图的顶点编号有时不是从 0 开始连续排列的，比如输入的顶点编号是业务编号 1、2、3、7、8 这种，用字典可以避免分配一个巨大的数组，也更贴近真实输入。

第三，为什么会写if v not in cost: continue？在标准多段图里不会出现，但一旦有跨段边，比如第 1 段的节点指向第 3 段的节点，我们按段号处理时第 3 段必然已经处理完，其实仍会在 cost 里。这条防线主要防止的是输入数据有误或段号混乱时程序崩掉，属于防御式编程。

第四，路径回溯依赖 nxt 数组。每个顶点只记录"下一步最优应该去哪"，最后从源点顺着 nxt 跳，就得到完整路径。如果你只想要最短长度，nxt 可以不存；但如果只是教学练习，我强烈建议每次都把路径打出来，因为"算出长度"和"得出路径"之间的差距，正好是实际工程里最容易掉链子的地方。

4.3 路径回溯：把最优决策链捞出来

路径回溯这个动作看起来是收尾，实际是验证算法正确性的最好手段。你算完 cost 之后，从源点出发，每次跳到 nxt[cur]，直到汇点。如果算出来的路径长度和 cost[source] 对不上，说明状态定义、转移方程或初始化里有问题。

多段图的路径回溯还有一个特点：因为段号严格递增，回溯出来的路径一定是逐段前进的，不可能跳段或者走回头路。这让你可以快速肉眼检查：路径的段号序列应该是 0,1,2,...,k-1，如果中间冒出一个相同的段号或者倒退，那几乎可以断定是 nxt 在某个节点记错了。

我平时调试这类算法，最喜欢把 cost 数组和 nxt 数组同时打印出来，然后沿路径手算一遍加和。这个过程比单看长度可靠得多，也更容易让初学者真正理解动态规划在做什么。

4.4 前向版本代码与对比

前向法的代码几乎是对称的，唯一的差别是它需要"入边"信息，也就是反向邻接表。我没有单独建反向表，而是用了一个辅助结构，从 graph 里还原出所有入边：

def build_reverse_graph(graph): rev = {} for u, edges in graph.items(): for v, w in edges: rev.setdefault(v, []).append((u, w)) return rev def multistage_dp_forward(graph, stages, source, sink): rev = build_reverse_graph(graph) cost = {source: 0} prv = {source: None} max_stage = max(stages.values()) nodes_by_stage = {} for node, stage in stages.items(): nodes_by_stage.setdefault(stage, []).append(node) for stage in range(1, max_stage + 1): for v in nodes_by_stage.get(stage, []): if v == source: continue best_cost = float('inf') best_prev = None for u, w in rev.get(v, []): if u not in cost: continue total = cost[u] + w if total < best_cost: best_cost = total best_prev = u cost[v] = best_cost prv[v] = best_prev path = [] cur = sink while cur is not None: path.append(cur) cur = prv.get(cur) path.reverse() return cost[sink], path

两种方法的时间复杂度和空间复杂度完全相同，都是 O(V+E) 的时间、O(V) 的空间。区别只在代码观感：后向法自然处理源点，前向法自然处理汇点。如果题目只有一个源点和一个汇点，爱用哪个都行；如果有一个源点多个汇点，前向法可以直接在多个汇点里取 min(cost[t])；如果有多个源点一个汇点，后向法更顺手。

5. 一个完整例子的手工推演

5.1 测试用例设计

我编一个能说明问题的测试图。它共 5 段，10 个顶点，段 0 只有源点 0，段 1 有顶点 1、2、3，段 2 有顶点 4、5、6，段 3 有顶点 7、8，段 4 只有汇点 9。完整边和权值见上面代码注释里的那张表。

这个用例我特意设计成不是"每段全连接"，而是每段只连后一段的一部分顶点，并且不同来源点连到同一后继时权值差异很大，这样手工算起来能区分出 DP 和贪心的区别。有些初学者一看"每段选最短边"就以为可以贪心，我强烈建议不要这样做，这个用例就是把贪心的反例给出来：0 到 1 的边权只有 1，很诱人，但 1 的后续边普遍偏贵，走它并不一定是全局最优。

5.2 逐段手算过程

现在我用后向法完整走一遍。先初始化 cost[9] = 0。

处理第 3 段，顶点 7 和 8：

• cost[7] = w(7,9) + cost[9] = 16 + 0 = 16
• cost[8] = w(8,9) + cost[9] = 4 + 0 = 4

处理第 2 段，顶点 4、5、6：

• cost[4] = min(18+16, 2+4) = min(34, 6) = 6，决策走 8
• cost[5] = min(10+16, 5+4) = min(26, 9) = 9，决策走 8
• cost[6] = min(2+16, 11+4) = min(18, 15) = 15，决策走 8

处理第 1 段，顶点 1、2、3：

• cost[1] = min(4+6, 11+9) = min(10, 20) = 10，决策走 4
• cost[2] = min(9+6, 5+9, 16+15) = min(15, 14, 31) = 14，决策走 5
• cost[3] = min(6+9, 13+15) = min(15, 28) = 15，决策走 5

处理第 0 段，源点 0：

• cost[0] = min(1+10, 2+14, 5+15) = min(11, 16, 20) = 11，决策走 1

所以最短路径长度是 11，路径是 0 -> 1 -> 4 -> 8 -> 9。顺着手算结果验证：1+4+2+4 = 11，和 cost[0] 完全一致。

这份手算过程其实就是动态规划表的填充过程。你可以看到每个顶点的计算都只依赖"更靠近汇点"的顶点，完全不需要回头修改前面的结果。这就是无后效性在最直观层面上的体现。

5.3 程序运行结果验证

把上面的代码跑一遍，输出应该是：

最短路径长度: 11 最短路径: 0 -> 1 -> 4 -> 8 -> 9

我把这个例子反复用于教学，因为它能同时验证好几件事：后向法的结果正确；路径回溯没有环；沿路径加和的权值等于 DP 算出的长度。这几条同时满足，基本可以确定代码没有逻辑问题。

如果你还想更彻底地验证正确性，可以把这张小图同时交给 Dijkstra 算法和 DP 各跑一遍，比对结果。我实测过，两者在这个例子里输出一致，但复杂度差别很明显：Dijkstra 用了优先队列，堆操作多，DP 一次线性扫描就完事。这个对比很直观，你可以自己在本地跑一次感受一下。

6. 常见问题排查与避坑实录

6.1 高频问题速查表

我把平时带人调试时遇到的高频问题整理成了一个速查表，实测命中率很高。

还有一个极其隐蔽的问题：处理多重边，也就是两个顶点之间有多条权值不同的边。邻接表里如果存了重复的 (v, w)，转移方程并不会错，因为 min 会自然筛掉较差的边，但图存储空间会浪费，调试时看邻接表也会迷惑。建议建图时直接去重，保留权值最小的那条。

6.2 调试这种题的几个心得体会

我在实际带新人的时候发现，多段图最短路径写错的人里，有将近一半不是不懂动态规划，而是栽在"建图和取边"这种工程细节上。比如把 (u, v, w) 存成了反的，比如读边的时候下标从 1 开始但遍历时从 0 开始，比如把顶点段号当成权重参与加法。所以我的建议很朴素：先花时间把图建对，再谈算法优化。

第二个体会是，手工推演小例子永远值得做。哪怕你已经在写生产级代码，遇到新算法也一定先拿一张不超过 10 个顶点的小图手算一遍，把每个中间值写下来。这个小动作能帮你确认状态定义是否合理、转移方向是否正确，省掉的排查时间远比花掉的多。

第三个体会是关于扩展的：这个题学会后，你可以很自然地把它的思路迁移到更长的问题链上。比如带资源约束的多阶段决策、模糊需求下的路径规划、甚至某些博弈类问题的逆向递推，本质都在用同一套"从终点往回拆"的思想。多段图只是给你一个最干净、最容易上手的载体，把这种思考方式练成本能，才是比代码本身更值钱的收获。

最后再分享一个我自己的习惯：代码里永远留一份"打印调试"的开关，把每次迭代里每个顶点的 cost 和决策打印出来。别因为看着啰嗦就删掉，实际排查问题的时候，一份完整的 DP 表比任何日志都管用。