最小环问题（有向图与无向图的 Floyd 算法求解）

问题描述

给定一个带权图（可以是有向图或无向图），图中可能包含正权、负权或零权边，但要求图中不存在负权环（因为如果存在负权环，最小环的权值可以趋于负无穷，问题无解）。我们需要找到图中权值最小的环（即最小环），并输出其权值。环的权值定义为环上所有边的权值之和。

核心思路

一种经典且高效的解法是利用 Floyd-Warshall 算法的动态规划思想。Floyd 算法原本用于求解所有顶点对之间的最短路径。我们可以巧妙地修改其状态定义和转移过程，使其在求解最短路径的同时，能够检测并记录经过特定顶点的最小环。

关键定义与原理

设图有 \(n\) 个顶点，顶点编号为 \(1\) 到 \(n\)。定义两个数组：

• \(dist[i][j]\)：表示从顶点 \(i\) 到顶点 \(j\) 的当前已知最短路径的长度（即 Floyd 算法中的标准距离数组）。
• \(g[i][j]\)：表示图中从顶点 \(i\) 到顶点 \(j\) 的直接边的权值。如果 \(i\) 和 \(j\) 之间没有直接边，则 \(g[i][j] = \infty\)。

最小环的构成：考虑一个最小环，它必然经过某个顶点 \(k\)。那么，这个环可以看作由三部分组成：

1. 从顶点 \(k\) 到顶点 \(i\) 的一条路径（不经过 \(k\) 本身）。
2. 从顶点 \(i\) 到顶点 \(j\) 的直接边（即 \(g[i][j]\)）。
3. 从顶点 \(j\) 回到顶点 \(k\) 的一条路径（不经过 \(k\) 本身）。
   并且，路径1和路径3在 Floyd 算法的迭代过程中，是由不经过顶点 \(k\) 的中间顶点（即编号小于 \(k\) 的顶点）所构成的最短路径。这正是 Floyd 算法“以 \(k\) 为中间点更新所有最短路径”时，\(dist[i][j]\) 所表示的含义。

因此，在 Floyd 算法的主循环中，当我们准备用顶点 \(k\) 作为中间点去更新所有 \(dist[i][j]\) 之前，此时的 \(dist[i][j]\) 表示的是“只使用编号小于 \(k\) 的顶点作为中间点”时，从 \(i\) 到 \(j\) 的最短路径长度。这时，对于所有的顶点对 \((i, j)\)（其中 \(i < k, j < k, i \neq j\)），我们可以检查：

\[\text{环的权值} = dist[i][j] + g[j][k] + g[k][i] \]

（注意，对于有向图，需要确认 \(g[j][k]\) 和 \(g[k][i]\) 都存在，即其权值不为无穷大。）
这个公式计算出的就是一个经过顶点 \(k\)，且以 \(i\) 和 \(j\) 作为 \(k\) 的相邻顶点的一个环的权值。我们在所有这样的 \(k, i, j\) 组合中取最小值，即可得到全局最小环的权值。

算法步骤详解

假设图的邻接矩阵已读入到数组 g 中，无边处用 INF（一个很大的数）表示，自身到自身的距离 g[i][i] = 0。

1. 初始化：

   • 创建 dist 数组，初始值完全拷贝 g 数组。这表示初始时，只考虑直接相连的边作为路径。
   • 初始化答案 ans = INF。

2. Floyd 算法主循环：

   对于 k 从 1 到 n：
        // 第一步：利用当前 dist 和顶点 k 更新最小环答案
        对于 i 从 1 到 k-1：
            对于 j 从 i+1 到 k-1：
                如果 dist[i][j] != INF 且 g[j][k] != INF 且 g[k][i] != INF：
                    candidate_cycle = dist[i][j] + g[j][k] + g[k][i]
                    更新 ans = min(ans, candidate_cycle)
   
        // 第二步：标准 Floyd 步骤，用顶点 k 作为中间点更新所有最短路径
        对于 i 从 1 到 n：
            如果 dist[i][k] == INF: 跳过本次循环
            对于 j 从 1 到 n：
                如果 dist[k][j] == INF: 跳过本次循环
                尝试用 i -> k -> j 这条路径更新 i 到 j 的最短距离：
                    new_dist = dist[i][k] + dist[k][j]
                    如果 new_dist < dist[i][j]：
                        dist[i][j] = new_dist
   

3. 输出结果：

   • 如果 ans == INF，说明图中不存在环（对于无向图，至少需要三条边才能构成环；对于有向图，至少需要两条边）。
   • 否则，ans 就是最小环的权值。

注意事项与示例

• 无向图处理：对于无向图，每条边在邻接矩阵 g 中是对称的，即 g[i][j] = g[j][i]。在更新答案时，公式 dist[i][j] + g[j][k] + g[k][i] 仍然适用，但要确保 i != j 且 i, j 都小于 k，以避免重复计算和自环的干扰。
• 负权边：算法可以处理负权边，但前提是图中不能有负权环。如果存在负权环，Floyd 算法本身在计算 dist 时可能会因为不断松弛而出现距离趋于负无穷的情况，导致结果错误。
• 路径记录：如果题目要求输出最小环的具体路径，我们需要额外维护一个 path 矩阵来记录最短路径的中间节点，在找到更小的环时，根据 dist[i][j] 和 k 来回溯出路径，但这会显著增加编码复杂度。
• 时间复杂度：与 Floyd 算法相同，为 \(O(n^3)\)。
• 空间复杂度：\(O(n^2)\)，用于存储 dist 和 g 矩阵。

简单示例

考虑一个无向图，4个顶点，边权如下：
1-2: 1
2-3: 2
3-1: 4
1-4: 5
3-4: 3

• 初始时，dist 和 g 相同。
• 当 k=3 时：
  • 考虑 i=1, j=2（均小于3）。dist[1][2] = 1（直接边），g[2][3] = 2, g[3][1] = 4。
  • 候选环权值 = 1 + 2 + 4 = 7。这对应环 1->2->3->1。
  • 这是算法找到的第一个环，更新 ans=7。
• 当 k=4 时：
  • 考虑 i=1, j=3。dist[1][3] 此时可能已被更新为经过顶点2的更短路径 1->2->3，权值为3。
  • g[3][4] = 3, g[4][1] = 5。
  • 候选环权值 = 3 + 3 + 5 = 11。这对应环 1->...->3->4->1。
  • 这个值大于当前的 ans=7，所以不更新。
  • 继续检查其他组合，可能发现更小的环（比如 1->3->4->1 的直接边环权值为4+3+5=12，也不是最小）。
• 最终 ans=7，即环 1-2-3-1 的权值。

总结

利用 Floyd-Warshall 算法求解最小环问题，是一种基于动态规划的巧妙方法。其核心在于，在 Floyd 算法逐步引入中间顶点 \(k\) 的过程中，利用当前已知的（不经过 \(k\) 的）最短路径 dist[i][j]，与两条直接边 g[j][k] 和 g[k][i] 相结合，来构造经过 \(k\) 的环。通过遍历所有可能的 \(k, i, j\) 组合，我们就能确保找到全局的最小环。这个方法对于顶点数不超过几百的稠密图非常有效。