Floyd-Warshall算法：循环顺序与正确实现解析

Floyd-Warshall算法是一种经典的动态规划算法，用于解决图中所有顶点对之间的最短路径问题。其核心在于通过迭代地考虑所有可能的中间节点来逐步优化路径。本文将详细探讨该算法的正确实现方式，特别是循环顺序的重要性，并分析常见的错误及其原因，确保读者能准确掌握其原理与实践。

Floyd-Warshall算法核心思想

Floyd-Warshall算法旨在计算加权图中任意两个顶点之间的最短路径。它通过考虑所有顶点作为中间节点，逐步更新任意两点间的距离。算法的精髓在于其动态规划思想：假设我们已经计算出所有只允许经过前 k-1 个顶点作为中间节点的最短路径，那么当允许经过第 k 个顶点作为中间节点时，任意两点 i 到 j 的最短路径要么是原来不经过 k 的最短路径，要么是经过 k 的路径（即 i 到 k 的最短路径加上 k 到 j 的最短路径）。

常见陷阱：错误的循环顺序

在实现Floyd-Warshall算法时，一个常见的错误是混淆了循环的顺序，特别是将代表中间节点的循环 k 放在了内层。考虑以下不正确的Java代码实现：

class Solution{
    public void shortest_distance(int[][] mat){
        int N = mat.length;

        // 错误的循环顺序：k在最内层
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < N; ++ j){
                for(int k = 0; k < N; ++k){ // k作为中间节点
                    // 检查路径是否存在且是否更短
                    if(mat[i][k] != -1 && mat[k][j] != -1 && (mat[i][j] == -1 || mat[i][j] > mat[i][k] + mat[k][j])){
                        mat[i][j] = mat[i][k] + mat[k][j];
                    }
                }
            }
        }
    }
}

这段代码的问题在于，当它尝试通过 k 作为中间节点更新 mat[i][j] 时，它假设 mat[i][k] 和 mat[k][j] 已经是最短路径。然而，由于 k 循环在 i 和 j 循环的内部，mat[i][k] 和 mat[k][j] 在当前迭代中可能还没有被完全优化。换句话说，当计算 mat[i][j] 时，路径 i -> k 和 k -> j 可能还没有考虑过所有小于 k 的中间节点，导致其值并非当前阶段的最优值，从而传递了不准确的中间结果。这种“状态”的依赖性没有得到正确满足。

正确实现：k 作为最外层循环

Floyd-Warshall算法的正确实现要求将代表中间节点的循环 k 放在最外层。这确保了在处理第 k 个中间节点时，所有涉及到的子路径（即 mat[i][k] 和 mat[k][j]）都已经通过考虑 0 到 k-1 的所有中间节点进行了优化。

class Solution{
    public void shortest_distance(int[][] mat){
        int N = mat.length;

        // 正确的循环顺序：k在最外层
        for(int k = 0; k < N; ++k){ // k作为中间节点
            for(int i = 0; i < N; ++i){ // i作为起点
                for(int j = 0; j < N; ++j){ // j作为终点
                    // 检查路径是否存在且是否更短
                    // mat[i][k] != -1 表示 i 到 k 有路径
                    // mat[k][j] != -1 表示 k 到 j 有路径
                    // mat[i][j] == -1 表示 i 到 j 之前没有路径或路径长度为无穷大
                    // mat[i][j] > mat[i][k] + mat[k][j] 表示通过 k 中转可以得到更短的路径
                    if(mat[i][k] != -1 && mat[k][j] != -1 && (mat[i][j] == -1 || mat[i][j] > mat[i][k] + mat[k][j])){
                        mat[i][j] = mat[i][k] + mat[k][j];
                    }
                }
            }
        }
    }
}

在这个正确的实现中：

1. 最外层循环 k：它迭代 0 到 N-1 的所有顶点，将每个顶点依次作为“中间节点”来考虑。
2. 内层循环 i 和 j：对于每一个确定的中间节点 k，算法遍历所有可能的起点 i 和终点 j。
3. 状态转移：mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])。当处理 k 时，mat[i][k] 和 mat[k][j] 已经代表了只允许经过 0 到 k-1 中间节点时的最短路径。通过这种方式，算法逐步构建并优化所有顶点对之间的最短路径，确保了动态规划状态的正确性。

注意事项

1. 初始距离矩阵：

   • mat[i][j] 初始化为 0 如果 i == j（到自身的距离为0）。
   • mat[i][j] 初始化为边的权重如果 i 到 j 有直接边。
   • mat[i][j] 初始化为 -1 (或一个很大的值，如 Integer.MAX_VALUE / 2，避免溢出) 如果 i 到 j 没有直接边。在给定的问题中，-1 表示没有直接路径。

2. 处理不可达路径：

   • 代码中的 mat[i][k] != -1 && mat[k][j] != -1 条件用于检查 i 到 k 和 k 到 j 的路径是否存在。如果任何一段路径不可达（用 -1 表示），则不能通过 k 中转。
   • mat[i][j] == -1 条件表示 i 到 j 当前是不可达的，或者之前没有找到任何路径，此时任何通过 k 的有效路径都将是更好的选择。

3. 时间复杂度： Floyd-Warshall算法的时间复杂度为 O(V^3)，其中 V 是图中顶点的数量。这是因为算法有三层嵌套循环，每层循环都遍历所有 V 个顶点。

4. 中间节点遍历顺序的灵活性： 虽然 k 必须是外层循环，但 k 自身的遍历顺序（例如 0 到 N-1，或者随机打乱）并不影响算法的最终正确性。只要所有节点都被依次作为中间节点考虑过一遍，最终结果都是正确的。这是因为每个 k 迭代都是基于前一个 k-1 迭代的结果，并独立于 k 的具体值。

   // 示例：打乱k的遍历顺序，结果依然正确
   import java.util.ArrayList;
   import java.util.Collections;
   import java.util.List;
   
   class Solution {
       public void shortest_distance(int[][] mat) {
           int N = mat.length;
           List nodes = new ArrayList<>();
           for (int i = 0; i < N; ++i) nodes.add(i);
           Collections.shuffle(nodes); // 随机打乱中间节点的顺序
   
           for (int l = 0; l < nodes.size(); ++l) {
               int k = nodes.get(l); // 获取当前中间节点
               for (int i = 0; i < N; ++i) {
                   for (int j = 0; j < N; ++j) {
                       if (mat[i][k] != -1 && mat[k][j] != -1 && (mat[i][j] == -1 || mat[i][j] > mat[i][k] + mat[k][j])) {
                           mat[i][j] = mat[i][k] + mat[k][j];
                       }
                   }
               }
           }
       }
   }

   这段代码证明了 k 循环的内部顺序无关紧要，关键是 k 必须在 i 和 j 循环之外，以确保每次迭代 k 时，mat[i][k] 和 mat[k][j] 都已经包含了所有通过先前中间节点（无论顺序如何）的优化信息。

总结

Floyd-Warshall算法是一个强大且直观的解决全源最短路径问题的工具。其正确性严格依赖于动态规划的状态转移方程和循环的正确顺序。核心要点是：代表中间节点的循环 k 必须位于最外层。这确保了在考虑通过 k 中转的路径时，所有 i 到 k 和 k 到 j 的子路径都已经通过考虑所有编号小于 k 的中间节点进行了充分优化。理解这一关键点是正确实现和应用Floyd-Warshall算法的基础。