企业官网建设流程全解析

1. 从一道经典题说起：为什么最小环问题值得单独拎出来讲

如果你刷过一段时间的算法题，一定见过这样一类问题：给出一张带权无向图，要求找出图中权值之和最小的环，并且把环上的节点按顺序输出。这类问题在竞赛和面试里出现的频率不算特别高，但一旦出现，往往就是区分度所在——因为很多人只会求最短路，却不知道怎么在求最短路的过程中顺手把最小环也处理掉。

POJ 1734 这道题就是最小环问题的教科书级入口。它的背景包装成了一个旅游路线规划的场景：给定若干城市之间的道路和距离，要求找出一条闭合的观光路线，使得总路程最短。剥掉这层包装，本质就是带权无向图的最小环问题，而且要求输出具体路径。

我第一次遇到这道题的时候，第一反应是枚举每条边，删掉它之后跑最短路，再加上这条边的权值，取最小值。这个思路没错，但复杂度是 O(E * 最短路复杂度)，对于稠密图来说开销相当可观。后来才意识到，Floyd 算法在它的三重循环结构里，天然就藏着一个求最小环的机会，只需要在正确的位置插入几行代码，就能在 O(N³) 的时间里同时完成最短路和最小环的求解。

这篇文章我会把整个思路拆开讲透：Floyd 求最小环的原理到底是什么、为什么循环顺序不能乱、路径怎么记录和还原、有哪些容易踩的坑。如果你正在准备算法竞赛，或者想把这个算法用到实际的路径规划场景里，这篇内容应该能帮你省下不少自己摸索的时间。

2. Floyd 求最小环的核心原理：循环顺序里藏着的秘密

2.1 先回顾 Floyd 在做什么

Floyd 算法的本质是动态规划。它的状态定义是：dis[i][j]表示从节点 i 到节点 j，只允许经过编号在 1 到 k 之间的中间节点时，所能得到的最短路径长度。当 k 从 1 枚举到 N 之后，dis[i][j]就是全局最短路径。

标准的三重循环长这样：

for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (dis[i][k] + dis[k][j] < dis[i][j]) dis[i][j] = dis[i][k] + dis[k][j];

关键在于理解每一轮 k 迭代开始之前，dis[i][j]里存的是什么。当外层循环进行到 k 的时候，dis[i][j]表示的是：从 i 到 j，只经过编号小于 k 的节点作为中间点时的最短距离。这一点非常重要，后面求最小环就靠它。

2.2 最小环的拆解思路

一个环，不管它长什么样，一定可以表示成这样的形式：环上编号最大的节点是 k，与 k 相邻的两个节点分别是 i 和 j（i、j 都小于 k），那么环的长度就是dis[i][j] + map[i][k] + map[k][j]。

这里dis[i][j]是 i 到 j 不经过 k 以及编号大于 k 的节点的最短距离，map[i][k]和map[k][j]是两条边的原始权值。为什么用map而不是dis？因为 i 到 k 和 k 到 j 必须是环上的直接相邻边，不能走更短的间接路径，否则就不构成一个简单环了。

那为什么这个公式能保证找到最小环？因为任何一个环都有唯一一个编号最大的节点，当我们枚举到这个最大节点 k 的时候，只要 i 和 j 之间的最短路径不经过 k（由于dis[i][j]此时只允许经过编号小于 k 的节点，自然不经过 k），那么dis[i][j] + map[i][k] + map[k][j]就恰好是这个环的长度。枚举所有可能的 k、i、j 组合，就能覆盖所有环。

2.3 循环顺序为什么不能颠倒

这是最容易出错的地方。正确的写法是在第 k 轮松弛之前，先用当前的dis数组去尝试更新最小环答案，然后再执行 Floyd 的松弛操作：

for (int k = 1; k <= n; k++) { // 第一步：用当前 dis 数组求最小环 for (int i = 1; i < k; i++) for (int j = i + 1; j < k; j++) if (dis[i][j] + map[i][k] + map[k][j] < ans) ans = dis[i][j] + map[i][k] + map[k][j]; // 第二步：正常的 Floyd 松弛 for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (dis[i][k] + dis[k][j] < dis[i][j]) dis[i][j] = dis[i][k] + dis[k][j]; }

如果你把求最小环的代码放到松弛之后，那么dis[i][j]可能已经经过了 k 节点，这时候再加上map[i][k]和map[k][j]，得到的就不是一个简单环了，可能会重复经过某些节点，算出来的值也没有意义。

我当初就是在这里栽了跟头。第一次写的时候觉得“反正都是枚举，放前面放后面应该差不多”，结果样例能过，提交上去一堆 WA。后来拿纸笔手动模拟了一遍才明白，松弛之后dis[i][j]的含义变了，整个公式的前提就不成立了。

记住一句话：求最小环必须在第 k 轮松弛之前做，用的是“只经过编号小于 k 的节点”的最短路信息。

3. 路径记录的完整方案：从只求长度到输出具体路线

3.1 为什么路径记录比求长度麻烦

求最小环的长度只需要维护一个最小值就行，但题目要求输出路径，这就需要在更新答案的时候，同时把对应的路径保存下来。路径记录有两种常见做法：一种是用pre数组记录前驱节点，另一种是用path数组记录中间经过的节点。在 Floyd 求最小环的场景下，用pre数组更直观。

pre[i][j]的定义是：从 i 到 j 的最短路径上，j 的前一个节点是谁。初始时，如果 i 和 j 之间有边，pre[i][j] = i；如果没有边，pre[i][j]可以设成 0 或者 -1 表示不可达。

当 Floyd 松弛发生的时候，如果dis[i][k] + dis[k][j] < dis[i][j]，说明找到了一条更短的路径，那么 j 的前驱就应该更新为pre[k][j]：

if (dis[i][k] + dis[k][j] < dis[i][j]) { dis[i][j] = dis[i][k] + dis[k][j]; pre[i][j] = pre[k][j]; }

3.2 更新答案时如何保存路径

当我们在第 k 轮发现一个更小的环时，需要把这个环的路径完整地记录下来。环的构成是：i 到 j 的最短路径（不经过 k），再加上 i-k 和 k-j 两条边。

所以路径可以这样拼：先从 j 出发，沿着pre[i][j]一路回溯到 i，得到 i 到 j 的路径（逆序），然后加上 k，再加上 i，形成一个完整的环。

if (dis[i][j] + map[i][k] + map[k][j] < ans) { ans = dis[i][j] + map[i][k] + map[k][j]; // 记录路径 path_len = 0; int t = j; while (t != i) { path[path_len++] = t; t = pre[i][t]; } path[path_len++] = i; path[path_len++] = k; }

这里回溯的过程需要特别注意：pre[i][t]表示的是从 i 到 t 的最短路径上 t 的前驱。当 t 等于 i 的时候停止，说明已经回溯到了起点。

3.3 输出顺序的调整

上面得到的path数组是从 j 回溯到 i，然后加上 k 和 i。输出的顺序需要根据题目要求调整。POJ 1734 要求按环的顺序输出节点编号，通常是从任意一个节点开始，沿着环走一圈。上面得到的路径顺序是 j → ... → i → k → (回到 j)，所以直接按这个顺序输出就是合法的环顺序。

但要注意，如果题目对输出起点有要求（比如从编号最小的节点开始），就需要额外做一次旋转操作。POJ 1734 没有这个要求，任意合法顺序都可以。

4. 初始化与边界处理：那些容易忽略的细节

4.1 邻接矩阵的初始化策略

Floyd 求最小环用的是邻接矩阵，初始化的时候需要区分三种情况：

• map[i][i] = 0：自己到自己的距离是 0
• map[i][j] = 边权：如果 i 和 j 之间有边
• map[i][j] = INF：如果 i 和 j 之间没有边

dis数组初始时和map完全一样。pre数组初始时，如果map[i][j]不是 INF 且 i 不等于 j，则pre[i][j] = i。

这里有一个坑：如果两个节点之间有多条边，应该保留权值最小的那条。POJ 1734 的数据里可能存在重边，如果不处理，用较大的边权去更新，答案就会偏大。

if (w < map[u][v]) { map[u][v] = map[v][u] = w; pre[u][v] = u; pre[v][u] = v; }

4.2 INF 的选取与溢出问题

INF 不能设得太大，否则dis[i][j] + map[i][k] + map[k][j]可能溢出。如果用的是 int 类型，INF 设成 0x3f3f3f3f 比较合适，因为两个 INF 相加不会溢出 int 的范围。三个 INF 相加也不会溢出，但结果会是一个很大的数，不会误更新答案。

如果你用的是 long long，INF 可以设成 1e18 左右，同样要注意加法溢出的问题。一个稳妥的做法是在做加法之前先判断是否有 INF：

if (dis[i][j] != INF && map[i][k] != INF && map[k][j] != INF) { int tmp = dis[i][j] + map[i][k] + map[k][j]; if (tmp < ans) { ... } }

4.3 自环和重边的处理

自环（i 到 i 的边）在最小环问题里通常不需要考虑，因为一个合法的环至少包含三个不同的节点。如果输入里有自环，直接忽略即可。

重边必须处理，取最小值。这一点在前面已经提到了，但值得再强调一次，因为很多人在写 Floyd 的时候习惯直接赋值，忘了比较。

4.4 无解情况的判断

如果整张图里不存在环，答案应该保持为 INF。输出的时候需要判断，如果ans == INF，说明无解，按照题目要求输出相应的提示信息。POJ 1734 的输出格式是No solution.，注意大小写和标点。

5. 完整代码实现与逐段解读

5.1 整体框架

下面给出一个完整的 C++ 实现，包含了输入处理、Floyd 求最小环、路径记录和输出：

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 105; const int INF = 0x3f3f3f3f; int n, m; int map[MAXN][MAXN]; int dis[MAXN][MAXN]; int pre[MAXN][MAXN]; int path[MAXN]; int path_len; int main() { while (scanf("%d%d", &n, &m) != EOF) { // 初始化 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { map[i][j] = (i == j) ? 0 : INF; dis[i][j] = (i == j) ? 0 : INF; pre[i][j] = (i == j) ? i : 0; } } // 读入边 for (int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); if (w < map[u][v]) { map[u][v] = map[v][u] = w; pre[u][v] = u; pre[v][u] = v; } } // 复制到 dis for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dis[i][j] = map[i][j]; int ans = INF; // Floyd 求最小环 for (int k = 1; k <= n; k++) { // 求最小环 for (int i = 1; i < k; i++) { for (int j = i + 1; j < k; j++) { if (dis[i][j] == INF || map[i][k] == INF || map[k][j] == INF) continue; int tmp = dis[i][j] + map[i][k] + map[k][j]; if (tmp < ans) { ans = tmp; path_len = 0; int t = j; while (t != i) { path[path_len++] = t; t = pre[i][t]; } path[path_len++] = i; path[path_len++] = k; } } } // Floyd 松弛 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (dis[i][k] == INF || dis[k][j] == INF) continue; if (dis[i][k] + dis[k][j] < dis[i][j]) { dis[i][j] = dis[i][k] + dis[k][j]; pre[i][j] = pre[k][j]; } } } } // 输出 if (ans == INF) { printf("No solution.\n"); } else { for (int i = 0; i < path_len; i++) { if (i > 0) printf(" "); printf("%d", path[i]); } printf("\n"); } } return 0; }

5.2 关键代码段解读

初始化部分：pre[i][j]在 i 等于 j 的时候设成 i，其他情况设成 0。这里设成 0 是为了在回溯的时候能够判断是否到达了起点。因为节点编号从 1 开始，0 不会和任何有效节点冲突。

求最小环部分：i 和 j 都从 1 枚举到 k-1，且 j 从 i+1 开始，避免重复枚举。因为环是无向的，i 到 j 和 j 到 i 是同一个环，只需要枚举一次。

路径回溯部分：从 j 开始，不断找pre[i][t]，直到 t 等于 i。这里有一个隐含的前提：i 到 j 之间必须存在路径，否则pre[i][t]可能是 0，导致死循环。所以在更新答案之前，先判断dis[i][j]是否为 INF。

松弛部分：标准的 Floyd 松弛，更新dis和pre。注意pre[i][j] = pre[k][j]这一行，含义是：从 i 到 j 经过 k 的路径上，j 的前驱和从 k 到 j 的路径上 j 的前驱是一样的。

5.3 多组数据的处理

POJ 1734 的输入可能包含多组测试数据，所以用while (scanf(...) != EOF)来循环读取。每次循环都需要重新初始化所有数组，这一点不能忘。我见过不少人因为忘了重置数组，导致第二组数据输出错误。

6. 实测中踩过的坑与排查思路

6.1 答案偏大：重边没有取最小值

这是最常见的错误。如果输入里存在 u 到 v 的多条边，而代码直接覆盖赋值，那么map[u][v]可能保存的是较大的那条边。求最小环的时候，用较大的边权去计算，答案自然偏大。

排查方法：在读完所有边之后，打印一下邻接矩阵，看看有没有哪两个节点之间的边权不是最小值。或者手动构造一组带重边的测试数据，对比预期输出。

6.2 路径输出错误：pre 数组更新时机不对

pre数组的更新必须和dis的更新同步进行。如果只更新了dis忘了更新pre，回溯出来的路径就是错的。还有一种情况是，在求最小环的时候用了pre数组，但此时pre数组还是上一轮的状态，导致路径不完整。

排查方法：在每次更新答案的时候，把回溯出来的路径打印出来，手动验证一下这条路径是否构成一个合法的环，环上的边是否都存在。

6.3 死循环：pre 数组回溯时遇到 0

如果dis[i][j]是 INF，说明 i 到 j 不可达，此时pre[i][j]可能是 0。如果代码没有判断 INF 就直接回溯，t = pre[i][t]会变成 0，然后pre[i][0]访问越界或者陷入死循环。

排查方法：在回溯之前加一个判断，确保dis[i][j] != INF。另外，可以在回溯循环里加一个计数器，如果回溯次数超过 n，说明出了问题，直接跳出。

6.4 循环顺序写反：先松弛后求环

前面已经强调过了，求最小环必须在松弛之前。如果你发现答案总是偏小，或者找到的“环”实际上重复经过了某些节点，大概率就是这个原因。

排查方法：把求最小环的代码块移到松弛之后，对比一下结果。如果结果变了，说明顺序确实影响了正确性。

6.5 输出格式错误：空格和换行

POJ 的题目对输出格式要求很严格。路径输出时，节点之间用空格分隔，最后一个节点后面不能有多余的空格，末尾要有换行。无解时输出No solution.，注意首字母大写，末尾有句点。

排查方法：用printf逐字符输出，或者用cout的时候注意不要多输出空格。可以本地用diff命令对比标准输出和你的输出。

7. 从 POJ 1734 延伸出去：最小环问题的变体与实战应用

7.1 有向图的最小环

有向图的最小环问题稍微不同。Floyd 同样适用，但公式变成dis[i][j] + map[j][i]，其中dis[i][j]是不经过 i 和 j 的最短路径。循环顺序依然是先求环后松弛，但 i 和 j 的枚举范围需要调整。

有向图最小环的一个经典应用是检测死锁：在资源分配图中，如果存在环，说明可能发生死锁。找到最小环可以帮助定位问题。

7.2 无权图的最小环

如果边权都是 1，可以用 BFS 来求最小环，复杂度是 O(N*(N+E))，对于稀疏图比 Floyd 的 O(N³) 更快。思路是枚举每个节点作为起点，做 BFS，当遇到已经访问过的节点时，就找到了一个环。

7.3 最小环在路径规划中的实际意义

回到 POJ 1734 的旅游路线背景，最小环问题在实际的路径规划里确实有应用。比如设计一条环形旅游路线，要求总路程最短；或者在物流配送中，规划一条闭合的配送路线，使得总行驶距离最小。这些场景都可以抽象成最小环问题。

当然，实际场景往往比这道题复杂得多，可能还需要考虑时间窗、载重限制、单行道等约束。但掌握了 Floyd 求最小环的基本思路，至少在面对小规模问题时，你能有一个可靠的解法。

7.4 性能优化的思路

Floyd 求最小环的复杂度是 O(N³)，对于 N 在 100 左右的图完全够用。如果 N 更大，就需要考虑其他算法，比如枚举每条边删掉后跑 Dijkstra，复杂度是 O(E * (N+E) log N)，对于稀疏图可能更快。

还有一种优化是在 Floyd 的内层循环里加剪枝：如果dis[i][k]已经是 INF，就不需要继续枚举 j 了。这个剪枝在稀疏图上效果比较明显。

8. 我个人的一些实操心得

写 Floyd 求最小环的代码，最核心的就是记住那个循环顺序：先求环，后松弛。这个顺序一旦搞反，整个算法的正确性就没了。我建议在写的时候，把求最小环的代码块用注释框起来，写上“必须在松弛之前”，这样下次复习的时候一眼就能看到。

路径记录的部分，pre数组的更新容易漏。我的习惯是在更新dis的同一行下面紧接着更新pre，这样不容易忘。回溯路径的时候，先判断dis[i][j]是否为 INF，再进入循环，可以避免很多边界问题。

关于 INF 的选取，0x3f3f3f3f 是一个很舒服的值，两个相加不会溢出，三个相加也不会。如果你用的是 Python，不用担心溢出问题，但要注意 INF 不要设得太大，否则加法运算会变慢。

最后，多组数据的题目一定要记得重置数组。我自己的做法是把初始化写成一个函数，每次循环开始的时候调用一次，这样比手动写循环更不容易出错。

如果你正在准备算法竞赛，建议把这道题反复写几遍，直到不看模板也能一气呵成。最小环问题虽然不算高频考点，但它是理解 Floyd 动态规划本质的一个很好的切入点。把这道题吃透了，你对 Floyd 的理解会上一个台阶。