企业官网建设流程全解析

1. 多段图最短路径到底在考什么

多段图最短路径问题，乍看像是一道普通的最短路，实际它是动态规划里非常典型的一类模型。题目通常会给出一张有向无环图，顶点被划分成若干个阶段，边只从当前阶段指向下一个阶段，源点在第一阶段，汇点在最后一个阶段。目标很明确：从源点走到汇点，让整条路径的边权之和最小。这个模型在算法题、数据结构课设、运筹学作业里都常见，尤其适合拿来练动态规划的“阶段划分”和“无后效性”这两个核心概念。

我第一次接触这类题时，脑子里第一反应是Dijkstra。后来把图一画才发现，多段图自带拓扑序，根本不需要优先队列。它每一个阶段只依赖前一个阶段的最优结果，状态转移非常干净。也就是说，你只要按阶段从左往右推，每个节点记录从源点到它的最短距离，最后汇点的值就是答案。相比一般图最短路，多段图DP的代码短、边界清楚、复杂度低，是理解动态规划的一把好钥匙。

这篇文章适合三类人：正在准备算法考试的学生、想补动态规划基础的开发者、以及需要把阶段决策问题写成程序的人。我会从建图、状态定义、递推公式、路径回溯、代码实现一直讲到常见坑和测试方法。你不需要先精通动态规划，只要知道数组和循环就能跟上。核心关键词就三个：多段图、最短路径、动态规划。把这三个词之间的关系吃透，这类题基本就稳了。

1.1 先把“多段图”画明白

多段图，英文常叫multistage graph，本质是一张有向无环图。它的顶点被分成k个互不相交的阶段，通常记作V1、V2、…、Vk。源点s在V1，汇点t在Vk。图中的每条边从某个阶段Vi的顶点指向阶段Vi+1的顶点，或者至少是从编号较小的阶段指向编号较大的阶段。正因为边只往“后面”走，图中不可能出现环，所以它天然满足动态规划对拓扑序的要求。

你可以把多段图想象成一条流水线：第一阶段是原料选择，第二阶段是粗加工，第三阶段是精加工，最后阶段是成品输出。每个阶段有若干可选节点，节点之间的边表示从一个状态转移到另一个状态的成本。你要做的不是随便走，而是按照阶段顺序一步一步选，最后让总成本最低。生活里类似的决策很多，比如项目分阶段采购、旅行按天规划路线、生产流程按工序选择设备，只要阶段之间不回头，都可以抽象成多段图。

这里有一个容易混淆的点：多段图不一定要求每个阶段节点数量相同，也不要求所有边都只连接相邻阶段。有些教材定义只允许相邻阶段连边，有些题目允许从第i阶段跳到第i+2甚至更后面。只要整体阶段编号递增，并且没有回头边，动态规划仍然成立。区别在于，如果允许跨阶段，你更新dp时不能只遍历上一阶段，而要按拓扑序更新所有可达后继。不过大多数考试题为了简化，都会限制成相邻阶段连边。

1.2 动态规划为什么比Dijkstra更贴题

Dijkstra当然能求多段图最短路，前提是边权非负。它的复杂度是O((V+E)logV)，用堆优化后也不差。但放在多段图上，Dijkstra有点“杀鸡用牛刀”。因为多段图的节点已经按阶段排好了，你不需要每次找当前距离最小的未访问节点，只需要按阶段顺序扫描。每个节点被访问一次，每条边被松弛一次，复杂度就是O(V+E)。对于节点数上万、边数几万的多段图，这个差距会很明显。

更关键的是，动态规划帮你保留了“阶段决策”的信息。Dijkstra只告诉你最终最短距离是多少，而多段图DP可以顺便记录每个节点是从哪个前驱来的，回溯出完整路径。如果你需要知道每个阶段选了哪个节点，或者需要统计最短路径条数，DP的扩展性更好。Dijkstra也能记录前驱，但它的松弛顺序是全局的，不像多段图这样一层一层推进，理解起来更绕。

我个人的判断标准很简单：如果图是有向无环图，并且节点能自然分层，优先考虑拓扑DP；如果图有环、边权非负、只求单源最短路，用Dijkstra；如果要求所有点对最短路，节点又不多，Floyd更省事。多段图最短路径问题属于第一类，所以标准解法就是动态规划，而不是把Dijkstra硬套上去。

1.3 这类题的输入长什么样

典型的题目输入会先给阶段数k、节点数n、边数m，然后给每个阶段包含哪些节点，最后给m条边，每条边是u、v、w，表示从u到v有一条权值为w的有向边。也有的题目直接给邻接矩阵，矩阵中第i行第j列是边权，无边用无穷大表示。还有的题目节点编号本身就按阶段排列，比如1到3是第一阶段，4到6是第二阶段，你不需要额外读阶段数组，只要按编号顺序更新即可。

输入格式不同，处理方式略有差别。如果给了阶段数组，那就按阶段数组的顺序遍历；如果没给阶段数组，但节点编号已经按阶段排好，直接从小到大遍历节点也能得到正确结果，因为所有边都指向编号更大的节点。最怕的是节点编号没按阶段排，边又乱给，这时你必须先按阶段信息确定拓扑序，否则DP会出错。我见过不少同学在这里翻车：图是连通的，边权也没问题，但答案偏大，原因就是某个节点的dp值还没算出来就被后继拿去用了。

另外要注意源点和汇点的位置。多数题默认源点是第一阶段唯一节点，汇点是最后一个阶段唯一节点。但有些题会有多个源点或多个汇点，这时可以加一个虚拟源点连向所有源点，边权为0，再加一个虚拟汇点，所有汇点连向它。这样做的好处是统一模型，不用在代码里写一堆特判。虚拟源点和虚拟汇点不改变最短路径的值，只是让DP的起点和终点更干净。

2. 动态规划建模：阶段、状态与递推

动态规划建模的第一步，永远是定义状态。多段图最短路径的状态定义非常直接：设dp[v]表示从源点s到节点v的最短距离。源点的dp[s]=0，其他节点初始化为无穷大。然后按照阶段顺序，对每个节点u，用它的所有出边去更新后继节点v：如果dp[u]+w(u,v)小于dp[v]，就更新dp[v]，同时记录pre[v]=u。这个过程从左往右推，最后dp[t]就是源点到汇点的最短路径长度。

这个递推式的正确性依赖于最优子结构。任何一条从s到t的最短路径，如果它经过节点v，那么从s到v的那一段也一定是从s到v的最短路径。否则你可以把更短的那段替换进去，得到一条更短的全局路径，矛盾。再加上多段图没有环，节点按阶段排列，计算dp[v]时它依赖的所有前驱都已经算完，所以不存在“用未来更新过去”的问题。这就是动态规划里说的无后效性。

如果你习惯从后往前思考，也可以定义反向状态：f[v]表示从节点v到汇点t的最短距离。汇点的f[t]=0，然后从最后一个阶段倒着往前推：f[u]=min{w(u,v)+f[v]}，其中v是u的后继。最后f[s]就是答案。向前推和向后推本质一样，只是方向不同。向前推更符合“从起点出发”的直觉，向后推在路径回溯时有时更方便。考试时选一种你顺手的就行，但不要两种混着写。

2.1 向前递推：从源点往汇点推

向前递推的公式可以写成：

dp[s] = 0 dp[v] = min{ dp[u] + w(u,v) }，其中u是v的前驱

实际写代码时，通常反过来遍历u的出边来更新v。按阶段从1到k-1，对当前阶段的每个节点u，如果dp[u]不是无穷大，就遍历它的所有出边(u,v,w)。这个顺序保证u的dp值已经确定，因为u的前驱都在更早的阶段。对于相邻阶段的多段图，当前阶段只会更新下一阶段；对于允许跨阶段的图，当前阶段可能更新后面多个阶段，但只要保证阶段递增，仍然正确。

这个写法有一个小优势：你不需要显式地写“min over前驱”。如果每个节点有多条入边，用出边更新会自动比较所有前驱。代码结构就是两层循环加一层边遍历，非常清晰。复杂度是O(V+E)，因为每个节点最多被处理一次，每条边最多被松弛一次。空间复杂度是O(V+E)，邻接表存图，dp和pre各一个数组。

需要注意，如果图中存在入度为0但不是源点的节点，它的dp会一直是无穷大，遍历它的出边时应该跳过。有些实现忘了判断dp[u]==INF，结果用无穷大去加权重，可能溢出或者得到错误值。尤其是用int时，INF加一个正数会溢出成负数，然后错误地更新其他节点。稳妥的做法是选一个足够大的INF，比如0x3f3f3f3f，并且在更新前检查dp[u]是否小于INF。

2.2 反向递推：从汇点往源点回推

反向递推的状态是f[v]：从v到汇点的最短距离。边界是f[t]=0，其他节点初始化为无穷大。然后按阶段从k-1倒着推到1，对每个节点u，遍历它的出边(u,v,w)，做：

f[u] = min(f[u], w + f[v])

最后f[s]就是答案。这种写法的好处是，当你要输出路径时，从s开始，每次选择一个满足w(u,v)+f[v]==f[u]的后继v，就能一路走到t。因为f[v]已经是从v到终点的最优值，所以沿着这个条件走，每一步都是最优决策。路径回溯不需要额外的pre数组，只需要一遍正向扫描。

反向递推在有些题目里更自然。比如题目要求输出从源点到汇点的路径，并且希望按字典序最小的路径，这时你可以从s开始，每次在满足等式的后继中选编号最小的那个，直接得到字典序最小路径。如果用向前递推，你需要先记录pre，再从t回溯，等长路径的处理会麻烦一些。两种方法都值得掌握，面试时如果面试官问你“能不能不记录前驱输出路径”，反向递推就是一个很好的回答。

不过反向递推也有一个细节：你必须确保所有后继的f值已经算好。对于多段图，按阶段倒序处理就能保证这一点。如果图不是按阶段存储，而是只给了邻接表，那你需要先做一次拓扑排序，或者按节点编号倒序处理（前提是编号满足拓扑序）。否则f[v]可能还是无穷大，导致f[u]更新错误。这个坑和向前递推是镜像的，本质都是拓扑序问题。

2.3 路径记录数组的细节

向前递推时，pre[v]记录的是“v是从哪个前驱来的”。初始化pre所有元素为-1，源点的pre保持-1。每次更新dp[v]时，令pre[v]=u。注意只有严格更短时才更新，还是等长时也更新，取决于题目要求。如果只求一条最短路径，严格更短更新即可；如果要求字典序最小路径，等长时可能要比较前驱编号或路径序列。大多数基础题只要求输出任意一条最短路径，所以严格更短更新就够了。

回溯时从汇点t开始，不断令cur=pre[cur]，直到cur变成-1或到达源点。把经过的节点存进数组，最后反转输出。这里有个常见错误：循环条件写成while(cur!=s)，但pre[s]可能是-1，导致死循环或者漏掉s。更稳的写法是while(cur!=-1)，在循环内把cur加入路径，如果cur==s就break。或者先判断pre[cur]!=-1再走。代码不长，但边界条件很多，建议单独写一个函数测试。

如果图中有多条最短路径，pre数组只保留最后更新它的那个前驱。由于我们按阶段顺序遍历，等长路径中后面被遍历到的前驱可能覆盖前面的，所以输出的路径不保证字典序。如果你需要特定顺序，可以在更新条件里加入额外判断：当dp[u]+w < dp[v]时直接更新；当dp[u]+w == dp[v]时，比较u和pre[v]的大小，或者比较完整路径。这个技巧在竞赛题里很常用，但基础题不用过度设计。

3. 手算一个多段图：把DP表铺开

光看公式容易飘，我们拿一个具体例子走一遍。假设有一张5阶段多段图，源点是1，汇点是10。阶段划分如下：阶段1只有节点1；阶段2有节点2、3、4；阶段3有节点5、6、7；阶段4有节点8、9；阶段5只有节点10。边和权重都是正数，具体如下表。我们先用向前递推算一遍，再用反向递推验证，最后回溯路径。

这个例子节点不多，但包含了汇合点、多条等长路径和路径选择，非常适合练手。手算时建议画一张表，每一行是一个阶段，每一列是一个节点，表格里填dp值。每填一个节点，标注它是从哪个前驱来的。这样算完一遍，路径自然就出来了。我备考时习惯用铅笔在纸上画，擦改方便，比直接在代码里调试快得多。

3.1 样例图与阶段划分

样例边如下：

所有边都从前一阶段指向后一阶段，符合多段图定义。源点1的dp[1]=0。阶段2的节点2、3、4只能从1来，所以dp[2]=2，dp[3]=4，dp[4]=3。接下来阶段3的节点5、6、7分别有来自2、3、4的入边，需要取最小值。再往后阶段4、阶段5同理。整张图没有环，也没有负权，但就算有负权，只要阶段顺序正确，这个DP依然能处理。

3.2 逐阶段更新距离

阶段3计算：

• 节点5：从2来是2+7=9，从3来是4+3=7，从4来是3+4=7，所以dp[5]=7，pre[5]可以记3或4。
• 节点6：从2来是2+4=6，从3来是4+2=6，从4来是3+1=4，所以dp[6]=4，pre[6]=4。
• 节点7：从2来是2+6=8，从3来是4+4=8，从4来是3+5=8，所以dp[7]=8，pre[7]可以记2、3或4。

阶段4计算：

• 节点8：从5来是7+3=10，从6来是4+6=10，从7来是8+7=15，所以dp[8]=10，pre[8]记5或6。
• 节点9：从5来是7+4=11，从6来是4+2=6，从7来是8+5=13，所以dp[9]=6，pre[9]=6。

阶段5计算：

• 节点10：从8来是10+3=13，从9来是6+4=10，所以dp[10]=10，pre[10]=9。

最终答案是从1到10的最短距离为10。你可以看到，阶段4的节点8虽然从两个前驱都能得到10，但节点9明显更优，最终汇点选择了节点9。这说明每一步局部最优不一定全局最优，但动态规划把所有可能都保留了，所以不会漏掉全局最优。

3.3 回溯路径与验证

从汇点10开始回溯：pre[10]=9，pre[9]=6，pre[6]=4，pre[4]=1。所以路径是1 -> 4 -> 6 -> 9 -> 10。验证权重：1到4是3，4到6是1，6到9是2，9到10是4，总和3+1+2+4=10，和dp[10]一致。这条路径在每个阶段都选了当时的最优前驱，但注意节点5和节点8也参与了竞争，最终被淘汰是因为后续边权更大。

如果你用反向递推，从汇点往前算f值：f[10]=0；f[8]=3，f[9]=4；f[5]=min(3+3,4+4)=6，f[6]=min(6+3,2+4)=6，f[7]=min(7+3,5+4)=10；f[2]=min(7+6,4+6,6+10)=13，f[3]=min(3+6,2+6,4+10)=9，f[4]=min(4+6,1+6,5+10)=7；f[1]=min(2+13,4+9,3+7)=10。结果同样是10。反向递推的f[1]=10，而且你可以从1开始，每次选择满足w+f[v]=f[u]的后继，得到1->4->6->9->10，路径一致。

手算一遍之后，你会发现多段图DP的计算量其实很小，核心就是按阶段填表。真正容易出错的地方不在公式，而在实现时的下标、初始化和遍历顺序。下一步我们把这些细节落到代码里。

4. 代码落地：C++和Python两套模板

写代码之前，先把输入输出格式定下来。为了通用，我建议用邻接表存图，用stage数组记录每个阶段包含哪些节点。节点编号从1开始，0号不用。源点默认为1，汇点默认为n。如果是多个源点或汇点，提前加虚拟点处理。dp数组初始化为INF，pre数组初始化为-1。然后按阶段从1到k-1遍历，对每个节点u，如果dp[u]不是INF，就遍历它的出边，更新后继。最后输出dp[n]和路径。

C++和Python的写法几乎一样，区别只在语法。C++适合竞赛，速度快；Python适合快速验证和面试手写。下面两套模板都经过我实际测试，直接替换边数据就能跑。注意代码中不要用mermaid，这里只有普通代码块。

4.1 C++邻接表写法

#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; int main() { int k, n, m; cin >> k >> n >> m; // 阶段数、节点数、边数 vector<vector<int>> stages(k + 1); for (int i = 1; i <= k; i++) { int cnt; cin >> cnt; for (int j = 0; j < cnt; j++) { int v; cin >> v; stages[i].push_back(v); } } vector<vector<pair<int,int>>> adj(n + 1); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); } vector<int> dp(n + 1, INF), pre(n + 1, -1); dp[1] = 0; for (int s = 1; s < k; s++) { for (int u : stages[s]) { if (dp[u] == INF) continue; for (auto [v, w] : adj[u]) { if (dp[u] + w < dp[v]) { dp[v] = dp[u] + w; pre[v] = u; } } } } cout << "最短距离: " << dp[n] << endl; vector<int> path; int cur = n; while (cur != -1) { path.push_back(cur); if (cur == 1) break; cur = pre[cur]; } reverse(path.begin(), path.end()); cout << "路径: "; for (int i = 0; i < (int)path.size(); i++) { if (i) cout << " -> "; cout << path[i]; } cout << endl; return 0; }

这段代码的关键点是按阶段遍历。阶段数组stages[1]到stages[k]分别存每个阶段的节点。循环只到k-1，因为最后一个阶段没有后继需要更新。如果某个节点dp为INF，说明从源点不可达，直接跳过。pre数组只在严格更短时更新，保证路径不会乱。最后从n回溯，如果图不连通，dp[n]可能是INF，路径数组也会异常，实际做题时要根据题目保证连通性。

4.2 Python写法与调试输出

INF = 10 ** 18 def solve(k, n, m, stages, edges): adj = [[] for _ in range(n + 1)] for u, v, w in edges: adj[u].append((v, w)) dp = [INF] * (n + 1) pre = [-1] * (n + 1) dp[1] = 0 for s in range(1, k): for u in stages[s]: if dp[u] == INF: continue for v, w in adj[u]: if dp[u] + w < dp[v]: dp[v] = dp[u] + w pre[v] = u print("最短距离:", dp[n]) path = [] cur = n while cur != -1: path.append(cur) if cur == 1: break cur = pre[cur] path.reverse() print("路径:", " -> ".join(map(str, path))) return dp[n], path # 样例数据 k = 5 n = 10 m = 20 stages = [ [], # 0号不用 [1], # 阶段1 [2, 3, 4], # 阶段2 [5, 6, 7], # 阶段3 [8, 9], # 阶段4 [10] # 阶段5 ] edges = [ (1, 2, 2), (1, 3, 4), (1, 4, 3), (2, 5, 7), (2, 6, 4), (2, 7, 6), (3, 5, 3), (3, 6, 2), (3, 7, 4), (4, 5, 4), (4, 6, 1), (4, 7, 5), (5, 8, 3), (5, 9, 4), (6, 8, 6), (6, 9, 2), (7, 8, 7), (7, 9, 5), (8, 10, 3), (9, 10, 4) ] solve(k, n, m, stages, edges)

Python版本更紧凑，适合在面试白板上手写。调试时可以在每轮阶段后打印dp数组，看看每个节点的值是否符合手算结果。比如在for s循环末尾加一行print(s, dp)，能快速定位哪一阶段开始偏大。注意INF要设得足够大，Python的整数不会溢出，但C++用int时要注意。如果边权可能达到1e9，节点数1e5，总和可能到1e14，这时得用long long。

4.3 滚动数组与空间优化

多段图有一个很好的性质：每个阶段只依赖前一个阶段，所以如果只求最短距离，不要求输出路径，可以用两个数组滚动更新。设dist表示当前阶段各节点的最短距离，next_dist表示下一阶段。遍历当前阶段的每个节点u，用dist[u]更新下一阶段的v。当前阶段处理完后，把next_dist赋给dist，清空next_dist。这样空间从O(V)降到O(最大阶段节点数)，对于阶段很宽的图能省不少内存。

但滚动数组有一个限制：它要求边只连接相邻阶段。如果允许跨阶段，你不能再只保留上一阶段，因为节点可能依赖更早阶段的值。这时候还是得老老实实用全局dp数组。另外，滚动数组不保留历史dp值，回溯路径会变得困难。如果需要输出路径，建议保留pre数组，或者用反向递推加正向扫描。工程里如果只关心数值，滚动数组是很好的优化；竞赛里如果内存限制宽松，用全局dp更省心。

我一般这样取舍：题目只问最短距离，节点数很大，用滚动数组；题目要求输出路径或统计方案数，用全局dp加pre。不要为了炫技把代码写复杂，多段图本身复杂度已经很低，可读性比省一点内存更重要。

5. 常见错误与排查清单

多段图DP的代码短，但短代码不代表不会错。我见过很多人在样例上跑对，一交就WA，最后发现是阶段顺序、初始化或路径记录的问题。这一章把典型错误整理成清单，你可以对照自己的代码逐条检查。每一条都是实际踩过的坑，不是泛泛而谈。

5.1 阶段顺序错乱：最隐蔽的WA

最隐蔽的错误是阶段顺序。如果你的节点编号没有按阶段排列，而你又直接写for u in 1..n去更新，就会出现某个节点的dp还没算出来，就被后继节点拿去用了。比如节点5属于阶段3，节点2属于阶段2，但编号5大于2，如果你按编号从小到大遍历，先遍历到节点2没问题，但假设某条边从阶段3指向阶段4，而阶段4的节点编号比阶段3小，按编号遍历就会先处理阶段4，导致它用到未更新的阶段3值。

解决方法是严格按阶段数组遍历，或者先对图做拓扑排序。如果你不想读阶段数组，也可以把所有节点按阶段编号排序，生成一个拓扑序，然后按这个顺序更新。很多题目默认节点编号就是拓扑序，但如果你不确定，最好显式处理。检查方法：打印每个节点的dp值，看看是否有节点的dp在它所有前驱之前就被更新了。更简单的方法是手算一个小样例，如果手算结果和程序一致，阶段顺序大概率没问题。

5.2 初始化与无穷大：老生常谈但总有人翻车

初始化错误主要有三种。第一种是把dp数组全部初始化为0，结果每个节点都从0开始加，答案当然错。第二种是INF设得太小，比如用1000000，但实际最短路径可能超过这个值。第三种是忘记把源点dp设为0，导致整个数组全是INF，最后输出INF。正确做法：dp所有元素初始化为INF，源点dp设为0，pre初始化为-1。INF可以选0x3f3f3f3f（约10亿），如果边权总和可能超过10亿，就改用0x3f3f3f3f3f3f3f3f或者LLONG_MAX/2。

还有一个细节：用INF去做加法时，如果INF是0x3f3f3f3f，加上一个正数不会溢出，但如果你用INT_MAX，加任何正数都会溢出成负数。所以要么在更新前判断dp[u] != INF，要么选一个安全的INF。我习惯在遍历出边前加一句if(dp[u] == INF) continue;，这样既避免溢出，也略微提升效率。Python没有溢出问题，但也要跳过INF，不然无穷大加权重还是无穷大，逻辑上没错，但可能掩盖不可达节点。

5.3 路径回溯：pre数组的三种错法

路径回溯的错法也很典型。第一种是pre更新条件写错，比如写成if(dp[u]+w <= dp[v])，等长路径不断覆盖，虽然不影响距离，但可能让pre指向一个同阶段节点，导致回溯时反复横跳。第二种是回溯循环条件写错，比如while(cur != 1)但pre[1]没设好，或者while(pre[cur] != -1)漏掉最后一个节点。第三种是忘记反转路径，输出从汇点到源点的倒序。检查方法：先验证路径上相邻节点之间确实有边，再把边权加起来看是否等于dp[n]。

我建议单独写一个getPath函数，输入pre数组和n，返回路径向量。在函数里先检查dp[n]是否为INF，如果是就返回空。然后从n开始，每次把cur加入路径，如果cur==1就break，否则cur=pre[cur]。如果cur变成-1还没到1，说明pre链断了，这时可以返回空或报错。最后反转路径。这个函数可以独立测试，不用每次都跑整个DP。

6. 对比与扩展：多段图DP还能怎么用

多段图最短路径问题虽然小，但它背后连着一大片知识点。你把它学透之后，可以自然扩展到最长路径、路径计数、字典序路径、资源约束DP等。在工程里，阶段决策、流水线调度、分层网络规划也会用到类似思路。这一章把多段图DP和其他最短路算法放一起对比，再聊聊常见的扩展方向，帮你建立知识网络。

6.1 和Dijkstra、Floyd、Bellman-Ford放一起看

从表里能看出，多段图DP和拓扑排序DP本质是一家人。多段图只是DAG的一种，特点在于节点天然分层，所以你不需要额外做拓扑排序，按阶段遍历就行。Dijkstra在多段图上也能用，但它没有利用阶段信息，复杂度更高。Floyd适合节点数很少且要求所有点对最短路的场景。Bellman-Ford适合有负权环检测的通用图，多段图没有环，用不上。

如果面试官问你“为什么不用Dijkstra”，你可以回答：Dijkstra的核心是每次选距离最小的未确定节点，而多段图的节点已经按阶段排好，距离最小的节点一定在当前阶段的最左端，不需要堆来维护。直接用阶段遍历，复杂度从O(ElogV)降到O(E)。这个回答既准确又体现你对算法本质的理解。

6.2 从最短路径扩展到最长路径与计数

多段图DP的框架很容易改。求最长路径时，把min改成max，dp初始化为负无穷，源点dp=0。因为图是无环的，最长路径不会无限增长，所以不需要担心正环。求最短路径条数时，增加一个cnt数组。当dp[u]+w < dp[v]时，dp[v]更新，cnt[v]=cnt[u]；当dp[u]+w == dp[v]时，cnt[v]+=cnt[u]。注意cnt可能会很大，竞赛题通常要求取模。求字典序最小路径时，可以在等长时比较路径序列，或者反向递推时每次选编号最小的后继。

这些扩展在考试里经常出现。比如“求最短路径有多少条”“求字典序最小的最短路径”“求经过节点数最少的最短路径”。核心思路都是保留多个状态，在转移时增加判断条件。多段图的结构让这些扩展变得很自然，因为每个阶段只依赖前一个阶段，不会出现循环依赖。

6.3 工程与竞赛里的典型场景

工程上，多段图模型可以描述很多阶段决策问题。比如项目分阶段采购设备，每个阶段有多个供应商，选择不同供应商的成本不同，阶段之间有兼容性约束，目标是最小化总成本。再比如旅行路线规划，把行程分成若干天，每天选择城市，城市之间的交通费用是边权，求总费用最小的路线。这些问题的共同点是阶段明确、决策有序、不能回头，正好是多段图的用武之地。

竞赛里，多段图最短路径经常作为动态规划入门题出现，也经常被包装成“机器人的路线选择”“流水线调度”“资源分配”等背景。有些题会结合状态压缩，比如每个阶段有多个任务，选择任务会消耗资源，要求资源不超过上限，这时就在多段图DP上加一维资源状态。还有些题会结合概率，求最大概率路径，把乘法换成加法取对数即可。万变不离其宗：按阶段划分状态，用前一阶段的最优值更新当前阶段。

7. 我的实操心得与测试建议

最后这部分聊聊我实际做这类题时的一些习惯。多段图DP不难，但想写得又快又对，还是得有一套自己的流程。我一般先画图，再手算两三个节点，确认递推式没错，然后写代码。代码写完后不急着交，先造几组边界数据跑一跑。下面这些经验都是踩坑之后总结的，你直接拿去用能省不少时间。

7.1 造测试数据：别只测样例

样例通常太顺，测不出问题。我习惯造这几类数据：第一类，只有一条路径的图，用来验证基本流程；第二类，有多条等长最短路径的图，用来检查pre覆盖和路径输出；第三类，存在不可达节点的图，用来检查INF处理；第四类，节点编号顺序和阶段顺序不一致的图，用来检查遍历顺序；第五类，边权为0或负数的图，用来检查INF和更新条件。每类数据手算一个预期结果，和程序输出对比。

举个例子，只有一条路径的图：1->2->3->4，权重都是1，答案应该是3，路径1->2->3->4。不可达图：1->2，3->4，源点1，汇点4，答案应该是INF，程序应该输出不可达而不是乱走。等长路径：1->2->4和1->3->4权重都是2，程序应该输出其中一条，距离为2。把这些数据都跑一遍，基本能覆盖90%的边界情况。

7.2 调试DP：打印表格比单步更有效

调试动态规划时，单步跟踪容易迷失在循环里。我更喜欢在每轮阶段结束后打印整个dp数组，然后和手算的表格对照。如果某一阶段开始出现偏差，就聚焦到那一阶段的节点，检查它的所有入边。比如手算dp[5]=7，程序输出9，说明更新节点5时用了错误的前驱，或者某个前驱的dp还没算好。这时可以把节点5的所有入边打印出来，看看每条边的dp[u]+w是多少。

另一个技巧是写一个print_dp函数，按阶段分组打印，而不是按节点编号打印。这样一眼就能看出哪个阶段的哪个节点出了问题。如果图比较大，还可以只打印当前阶段的节点和后继节点。Python里可以用pprint，C++里就手动格式化。调试代码不用写得漂亮，能快速定位问题就行。

7.3 面试或课堂讲解的顺序

如果面试被问到这道题，我建议按这个顺序讲：先定义多段图，说明它是有向无环图且节点分层；然后定义状态dp[v]为源点到v的最短距离；写出递推式dp[v]=min(dp[u]+w)；说明按阶段遍历保证拓扑序，复杂度O(V+E)；再提一下路径回溯用pre数组；最后对比Dijkstra，强调多段图DP的优势。这样讲逻辑清楚，面试官能看出你不仅会写代码，还理解为什么这么写。

课堂上讲解时，可以先用一个生活例子引入，比如“从家到公司要经过几个换乘点，每个换乘点有不同路线，怎么选总时间最短”。然后画图，标出阶段，带着学生手算一遍。手算之后再上代码，学生更容易接受。我试过这种讲法，比直接甩公式效果好得多。多段图最短路径问题本身不难，难的是让初学者理解“阶段”和“无后效性”，所以例子越具体越好。

我自己现在遇到这类题，第一反应就是先画阶段图，把源点和汇点标出来，然后从源点开始一层一层往右推。推的时候顺手在纸上记下每个节点的dp值和前驱，算完汇点，路径也自然出来了。这套流程用熟了，基本不会出错。如果你刚开始学，建议也用手算几遍，再动手写代码，比直接抄模板理解得深。