最小环问题（Floyd 算法在无向和有向图中的解法）

字数 4942 2025-12-16 22:14:02

最小环问题（Floyd 算法在无向和有向图中的解法）

我将为你详细讲解如何求解图中最小环（即总边权最小的简单环）的问题，重点介绍基于 Floyd 算法的经典解法。

问题描述

给定一个带权图（有向或无向），图中可能包含负权边，但没有负权环（否则最小环的权值可以趋于负无穷，问题无意义）。目标是找出图中所有简单环（没有重复顶点的环）中，总边权之和最小的那个环的权值，有时也要求输出构成该环的顶点序列。

算法核心思想

Floyd-Warshall 算法原本用于求解所有顶点对之间的最短路径。我们可以巧妙地利用其动态规划的过程，在计算最短路径的同时，以每个顶点作为中间点，尝试构造经过该点的环，从而检测出最小环。

算法步骤详解

步骤1：初始化距离矩阵

设图有 \(n\) 个顶点，编号从 1 到 \(n\)。
初始化一个 \(n \times n\) 的距离矩阵 dist，其中 dist[i][j] 表示从顶点 i 到顶点 j 的当前已知最短路径长度。
初始时：
- 如果 i 到 j 有直接边，则 dist[i][j] 设为该边的权值。
- 如果 i 等于 j，则 dist[i][j] = 0（自环通常不考虑，除非题目特别说明）。
- 否则，dist[i][j] 设为无穷大（表示尚未发现路径）。

步骤2：记录初始直接连接

我们需要保存初始的直接边权，因为在后续更新中，dist 矩阵会不断被最短路径更新，原始的直接边信息可能会丢失。但计算环时需要用到“原始边”来闭合环。
因此，我们另外保存一个初始距离矩阵 original，它就是我们步骤1中初始化的 dist 矩阵的副本。original[i][j] 始终表示从 i 到 j 的直接边的权值（无边则为无穷大）。

步骤3：Floyd 动态规划与环检测

Floyd 算法的核心是一个三重循环，最外层循环变量 k 表示“允许使用顶点 1, 2, ..., k 作为中间点”。

在更新 dist[i][j] 之前（即尝试用 k 作为中间点松弛 i 到 j 的路径之前），我们可以利用当前已知的信息尝试构造一个环。
考虑一个环，它由顶点 i 到 j 的一条路径，以及从 j 直接返回 i 的一条边构成。当前，我们已知（在使用 k 作为中间点之前）：
- dist[i][j]：表示从 i 到 j，只经过编号小于 k 的中间点的最短路径长度。
- original[j][i]：表示从 j 直接到 i 的边的权值（即闭合环的那条边）。
如果 dist[i][j] 和 original[j][i] 都不是无穷大，那么我们就发现了一个经过顶点 i, j, 并且以 k 作为最大编号中间点（注意：这个环本身并不一定经过 k，但我们的检测时机保证了 i 和 j 都小于等于 k，且路径上的中间点都小于 k）的候选环。其权值为：cycle_weight = dist[i][j] + original[j][i]。
我们用这个权值去更新全局的最小环答案 min_cycle。

为什么能保证检测到所有环？
因为 k 是从 1 递增到 n 的。对于任何一个简单环，我们总可以找到这个环中编号最大的顶点，设为 \(k_{max}\)。在这个环中，存在两个与 \(k_{max}\) 相邻的顶点 i 和 j（在环上，i 和 j 都与 \(k_{max}\) 直接相连，且 i 和 j 的编号都小于 \(k_{max}\)）。当 Floyd 算法外层循环 \(k = k_{max}\) 时，在更新之前，dist[i][j] 已经计算出了不经过 \(k_{max}\) 以及任何编号大于 i, j 的顶点的 i 到 j 的最短路径，这条路径恰好就是这个环去掉顶点 \(k_{max}\) 和两条邻边后剩下的部分。此时，original[j][i] 提供了闭合环的那条边（注意在有向图中，这条边是 j->i；在无向图中，original[j][i] 等于 original[i][j]，代表同一条无向边）。这样，我们就检测到了这个环。

步骤4：更新最短路径

在完成对当前 k 的所有 (i, j) 对的环检测后，我们正常执行 Floyd 算法的松弛操作：
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。
然后 k 加 1，重复步骤3和步骤4，直到 k 遍历完所有顶点。

算法流程总结

初始化 dist 矩阵和 original 矩阵。
初始化 min_cycle = INF（一个很大的数）。
对于 k 从 1 到 n：
1. 对于所有 i < k 且 j < k 且 i != j：
  - 如果 dist[i][j] + original[j][i] < min_cycle，则更新 min_cycle。
2. 对于所有 i 从 1 到 n：
  - 对于所有 j 从 1 到 n：
    - 如果 dist[i][k] + dist[k][j] < dist[i][j]，则更新 dist[i][j]。
循环结束后，如果 min_cycle 仍然为 INF，则说明图中没有环；否则 min_cycle 即为最小环的权值。

时间复杂度与空间复杂度

时间复杂度：与 Floyd-Warshall 算法相同，为 \(O(n^3)\)，其中 n 是顶点数。因为我们在三重循环内部只增加了常数时间的判断。
空间复杂度：\(O(n^2)\)，用于存储两个 \(n \times n\) 的矩阵。

示例演示（无向图）

考虑一个 4 个顶点的无向图，边权如下（邻接矩阵）：

初始 dist 和 original:
    1   2   3   4
1   0   1  INF  3
2   1   0   2  INF
3 INF   2   0   4
4   3 INF   4   0

算法过程简述：

k=1: 没有 i<1, j<1，跳过检测。用顶点1松弛其他距离，但本例中无更新。
k=2: 检测 i=1, j=1? 不，i!=j。i=1, j=1? 无效。实际上，当 k=2 时，我们检测 i=1, j=1? 不行。我们检测所有 i<2, j<2，即只有 i=1, j=1，无效。之后用顶点2松弛，更新 dist[1][3] = min(INF, 1+2)=3。
k=3: 检测 i<3, j<3 且 i!=j 的顶点对。
- (i=1, j=2): dist[1][2] + original[2][1] = 1 + 1 = 2。这是一个环 1-2-1？不对，这是由边(1,2)和边(2,1)构成的环，但在无向图中，这其实是同一条边走了两次，不是简单环。这里暴露了一个问题：我们需要确保 i 到 j 的路径 dist[i][j] 不包含直接边 (i, j)，否则会重复计算边。在经典实现中，我们通常要求 dist[i][j] 是不经过顶点 k 及更大编号顶点的路径，但它可能包含直接边。为了避免将两条边（i-j 的直接边和 j-i 的直接边）当成一个环，我们需要确保在计算环时，i 到 j 的路径至少包含一个中间顶点。在 k=3 时，dist[1][2] 的值是 1，这正是直接边，它不经过任何中间点。所以这个“环” 1-2-1 是无效的。正确的检测应该是在我们计算环时，确保 dist[i][j] 是不经过 k 的、且至少包含一个中间点的最短路径。实际上，在 Floyd 的经典最小环算法中，我们通常不将 i 和 j 都限制为小于 k，而是在 k 的循环内，先检测所有 i 和 j（i 和 j 都不等于 k，且 i<j 以避免重复计算无向图的同一条边两次），候选环为 dist[i][j] + original[i][k] + original[k][j]。这个环由三部分组成：从 i 到 j 不经过 k 的最短路径（dist[i][j]），以及从 k 到 i 的直接边，从 k 到 j 的直接边。这样就保证了环至少有三个顶点，是简单环。
让我们纠正并重新描述更常见的无向图最小环 Floyd 算法：

无向图最小环的标准 Floyd 解法

初始化 dist 和 original 同前。
初始化 min_cycle = INF。
对于 k 从 1 到 n：
1. 对于所有 i < k 且 j < k 且 i != j：
  - 如果 original[i][k] != INF 且 original[k][j] != INF 且 dist[i][j] != INF：
    - cycle_weight = dist[i][j] + original[i][k] + original[k][j]
    - 更新 min_cycle = min(min_cycle, cycle_weight)
2. 用顶点 k 松弛所有顶点对的最短路径：对于所有 i, j，dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。

为什么这个是正确的？
当外层循环到 k 时，dist[i][j] 保存的是从 i 到 j 且中间只经过编号小于 k 的顶点的最短路径长度。那么，如果我们有一条从 i 到 k 的直接边，和一条从 k 到 j 的直接边，再加上一条从 i 到 j 的、不经过 k 的路径，这三部分就构成了一个经过顶点 k 的环。因为 i 和 j 都小于 k，且路径上的中间点编号也小于 k，所以这个环的最大编号顶点就是 k。通过遍历所有可能的 i, j (<k)，我们就能找出所有以 k 为最大编号顶点的环，并更新最小环答案。

有向图的最小环

对于有向图，算法需要调整。因为环的方向性，我们不能简单地用 original[i][k] + original[k][j] 来连接 k 到 i 和 k 到 j。一种通用的方法是使用最开始时描述的逻辑：在 Floyd 主循环中，在更新 dist[i][j] 之前，检查 dist[i][j] + original[j][i] 是否构成一个环（即 i 到 j 的路径，加上 j 到 i 的直接边）。但同样要注意避免路径是直接边的情况（即 i 直接到 j）。我们可以通过要求 i, j, k 互不相同，并且在检测时，确保 i 和 j 都在当前 k 的范围内，并且 dist[i][j] 是不经过 k 的路径（在 Floyd 算法中，当我们在 k 循环内检测时，当前的 dist[i][j] 正好是不经过 k 的）。更稳健的实现是：
在 k 循环内，对于所有 i 和 j（i, j, k 互不相同）：
如果 dist[i][j] != INF 且 original[j][k] != INF 且 original[k][i] != INF，则 cycle_weight = dist[i][j] + original[j][k] + original[k][i] 是一个经过 i, j, k 的环（顺序为 k -> i -> ... -> j -> k）。

最终建议

对于无向图最小环，使用标准 Floyd 变体，检测环的公式为：dist[i][j] + original[i][k] + original[k][j]，其中 i < k, j < k, i != j。
对于有向图最小环，可以使用检测公式：dist[i][j] + original[j][k] + original[k][i]，其中 i, j, k 互不相同，且在 k 循环内，dist[i][j] 是不经过 k 的最短路径。
算法结束后，如果 min_cycle 为 INF，则图中无环；否则即为最小环的权值和。

这个算法优雅地复用了 Floyd-Warshall 的动态规划框架，在 \(O(n^3)\) 时间内解决了最小环问题，是竞赛和面试中的经典考题。

最小环问题（Floyd 算法在无向和有向图中的解法）我将为你详细讲解如何求解图中最小环（即总边权最小的简单环）的问题，重点介绍基于 Floyd 算法的经典解法。问题描述给定一个带权图（有向或无向），图中可能包含负权边，但没有负权环（否则最小环的权值可以趋于负无穷，问题无意义）。目标是找出图中所有简单环（没有重复顶点的环）中，总边权之和最小的那个环的权值，有时也要求输出构成该环的顶点序列。算法核心思想 Floyd-Warshall 算法原本用于求解所有顶点对之间的最短路径。我们可以巧妙地利用其动态规划的过程，在计算最短路径的同时，以每个顶点作为中间点，尝试构造经过该点的环，从而检测出最小环。算法步骤详解步骤1：初始化距离矩阵设图有 \( n \) 个顶点，编号从 1 到 \( n \)。初始化一个 \( n \times n \) 的距离矩阵 dist ，其中 dist[i][j] 表示从顶点 i 到顶点 j 的当前已知最短路径长度。初始时：如果 i 到 j 有直接边，则 dist[i][j] 设为该边的权值。如果 i 等于 j，则 dist[i][j] = 0 （自环通常不考虑，除非题目特别说明）。否则， dist[i][j] 设为无穷大（表示尚未发现路径）。步骤2：记录初始直接连接我们需要保存初始的直接边权，因为在后续更新中， dist 矩阵会不断被最短路径更新，原始的直接边信息可能会丢失。但计算环时需要用到“原始边”来闭合环。因此，我们另外保存一个初始距离矩阵 original ，它就是我们步骤1中初始化的 dist 矩阵的副本。 original[i][j] 始终表示从 i 到 j 的直接边的权值（无边则为无穷大）。步骤3：Floyd 动态规划与环检测 Floyd 算法的核心是一个三重循环，最外层循环变量 k 表示“允许使用顶点 1, 2, ..., k 作为中间点”。在更新 dist[i][j] 之前（即尝试用 k 作为中间点松弛 i 到 j 的路径之前），我们可以利用当前已知的信息尝试构造一个环。考虑一个环，它由顶点 i 到 j 的一条路径，以及从 j 直接返回 i 的一条边构成。当前，我们已知（在使用 k 作为中间点之前）： dist[i][j] ：表示从 i 到 j，只经过编号小于 k 的中间点的最短路径长度。 original[j][i] ：表示从 j 直接到 i 的边的权值（即闭合环的那条边）。如果 dist[i][j] 和 original[j][i] 都不是无穷大，那么我们就发现了一个经过顶点 i, j, 并且以 k 作为最大编号中间点（注意：这个环本身并不一定经过 k，但我们的检测时机保证了 i 和 j 都小于等于 k，且路径上的中间点都小于 k ）的候选环。其权值为： cycle_weight = dist[i][j] + original[j][i] 。我们用这个权值去更新全局的最小环答案 min_cycle 。为什么能保证检测到所有环？因为 k 是从 1 递增到 n 的。对于任何一个简单环，我们总可以找到这个环中编号最大的顶点，设为 \( k_ {max} \)。在这个环中，存在两个与 \( k_ {max} \) 相邻的顶点 i 和 j（在环上，i 和 j 都与 \( k_ {max} \) 直接相连，且 i 和 j 的编号都小于 \( k_ {max} \)）。当 Floyd 算法外层循环 \( k = k_ {max} \) 时，在更新之前， dist[i][j] 已经计算出了不经过 \( k_ {max} \) 以及任何编号大于 i, j 的顶点的 i 到 j 的最短路径，这条路径恰好就是这个环去掉顶点 \( k_ {max} \) 和两条邻边后剩下的部分。此时， original[j][i] 提供了闭合环的那条边（注意在有向图中，这条边是 j->i；在无向图中， original[j][i] 等于 original[i][j] ，代表同一条无向边）。这样，我们就检测到了这个环。步骤4：更新最短路径在完成对当前 k 的所有 (i, j) 对的环检测后，我们正常执行 Floyd 算法的松弛操作： dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 。然后 k 加 1，重复步骤3和步骤4，直到 k 遍历完所有顶点。算法流程总结初始化 dist 矩阵和 original 矩阵。初始化 min_cycle = INF （一个很大的数）。对于 k 从 1 到 n：对于所有 i < k 且 j < k 且 i != j：如果 dist[i][j] + original[j][i] < min_cycle ，则更新 min_cycle 。对于所有 i 从 1 到 n：对于所有 j 从 1 到 n：如果 dist[i][k] + dist[k][j] < dist[i][j] ，则更新 dist[i][j] 。循环结束后，如果 min_cycle 仍然为 INF，则说明图中没有环；否则 min_cycle 即为最小环的权值。时间复杂度与空间复杂度时间复杂度：与 Floyd-Warshall 算法相同，为 \( O(n^3) \)，其中 n 是顶点数。因为我们在三重循环内部只增加了常数时间的判断。空间复杂度：\( O(n^2) \)，用于存储两个 \( n \times n \) 的矩阵。示例演示（无向图）考虑一个 4 个顶点的无向图，边权如下（邻接矩阵）：算法过程简述： k=1: 没有 i<1, j <1，跳过检测。用顶点1松弛其他距离，但本例中无更新。 k=2: 检测 i=1, j=1? 不，i!=j。i=1, j=1? 无效。实际上，当 k=2 时，我们检测 i=1, j=1? 不行。我们检测所有 i<2, j<2，即只有 i=1, j=1，无效。之后用顶点2松弛，更新 dist[1][3] = min(INF, 1+2)=3 。 k=3: 检测 i<3, j<3 且 i !=j 的顶点对。 (i=1, j=2): dist[1][2] + original[2][1] = 1 + 1 = 2 。这是一个环 1-2-1？不对，这是由边(1,2)和边(2,1)构成的环，但在无向图中，这其实是同一条边走了两次，不是简单环。这里暴露了一个问题：我们需要确保 i 到 j 的路径 dist[i][j] 不包含直接边 (i, j)，否则会重复计算边。在经典实现中，我们通常要求 dist[i][j] 是不经过顶点 k 及更大编号顶点的路径，但它可能包含直接边。为了避免将两条边（i-j 的直接边和 j-i 的直接边）当成一个环，我们需要确保在计算环时，i 到 j 的路径至少包含一个中间顶点。在 k=3 时， dist[1][2] 的值是 1，这正是直接边，它不经过任何中间点。所以这个“环” 1-2-1 是无效的。正确的检测应该是在我们计算环时，确保 dist[i][j] 是不经过 k 的、且至少包含一个中间点的最短路径。实际上，在 Floyd 的经典最小环算法中，我们通常不将 i 和 j 都限制为小于 k ，而是在 k 的循环内，先检测所有 i 和 j（i 和 j 都不等于 k，且 i<j 以避免重复计算无向图的同一条边两次），候选环为 dist[i][j] + original[i][k] + original[k][j] 。这个环由三部分组成：从 i 到 j 不经过 k 的最短路径（ dist[i][j] ），以及从 k 到 i 的直接边，从 k 到 j 的直接边。这样就保证了环至少有三个顶点，是简单环。让我们纠正并重新描述更常见的无向图最小环 Floyd 算法：无向图最小环的标准 Floyd 解法初始化 dist 和 original 同前。初始化 min_cycle = INF 。对于 k 从 1 到 n：对于所有 i < k 且 j < k 且 i != j：如果 original[i][k] != INF 且 original[k][j] != INF 且 dist[i][j] != INF ： cycle_weight = dist[i][j] + original[i][k] + original[k][j] 更新 min_cycle = min(min_cycle, cycle_weight) 用顶点 k 松弛所有顶点对的最短路径：对于所有 i, j， dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 。为什么这个是正确的？当外层循环到 k 时， dist[i][j] 保存的是从 i 到 j 且中间只经过编号小于 k 的顶点的最短路径长度。那么，如果我们有一条从 i 到 k 的直接边，和一条从 k 到 j 的直接边，再加上一条从 i 到 j 的、不经过 k 的路径，这三部分就构成了一个经过顶点 k 的环。因为 i 和 j 都小于 k，且路径上的中间点编号也小于 k，所以这个环的最大编号顶点就是 k。通过遍历所有可能的 i, j ( <k)，我们就能找出所有以 k 为最大编号顶点的环，并更新最小环答案。有向图的最小环对于有向图，算法需要调整。因为环的方向性，我们不能简单地用 original[i][k] + original[k][j] 来连接 k 到 i 和 k 到 j。一种通用的方法是使用最开始时描述的逻辑：在 Floyd 主循环中，在更新 dist[i][j] 之前，检查 dist[i][j] + original[j][i] 是否构成一个环（即 i 到 j 的路径，加上 j 到 i 的直接边）。但同样要注意避免路径是直接边的情况（即 i 直接到 j）。我们可以通过要求 i, j, k 互不相同，并且在检测时，确保 i 和 j 都在当前 k 的范围内，并且 dist[i][j] 是不经过 k 的路径（在 Floyd 算法中，当我们在 k 循环内检测时，当前的 dist[i][j] 正好是不经过 k 的）。更稳健的实现是：在 k 循环内，对于所有 i 和 j（i, j, k 互不相同）：如果 dist[i][j] != INF 且 original[j][k] != INF 且 original[k][i] != INF ，则 cycle_weight = dist[i][j] + original[j][k] + original[k][i] 是一个经过 i, j, k 的环（顺序为 k -> i -> ... -> j -> k）。最终建议对于无向图最小环，使用标准 Floyd 变体，检测环的公式为： dist[i][j] + original[i][k] + original[k][j] ，其中 i < k, j < k, i != j。对于有向图最小环，可以使用检测公式： dist[i][j] + original[j][k] + original[k][i] ，其中 i, j, k 互不相同，且在 k 循环内， dist[i][j] 是不经过 k 的最短路径。算法结束后，如果 min_cycle 为 INF，则图中无环；否则即为最小环的权值和。这个算法优雅地复用了 Floyd-Warshall 的动态规划框架，在 \( O(n^3) \) 时间内解决了最小环问题，是竞赛和面试中的经典考题。