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];
}
}
}
}
}
}在这个正确的实现中：
- 最外层循环 k：它迭代 0 到 N-1 的所有顶点，将每个顶点依次作为“中间节点”来考虑。
- 内层循环 i 和 j：对于每一个确定的中间节点 k，算法遍历所有可能的起点 i 和终点 j。
- 状态转移：mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])。当处理 k 时，mat[i][k] 和 mat[k][j] 已经代表了只允许经过 0 到 k-1 中间节点时的最短路径。通过这种方式，算法逐步构建并优化所有顶点对之间的最短路径，确保了动态规划状态的正确性。
注意事项
-
初始距离矩阵：
- mat[i][j] 初始化为 0 如果 i == j（到自身的距离为0）。
- mat[i][j] 初始化为边的权重如果 i 到 j 有直接边。
- mat[i][j] 初始化为 -1 (或一个很大的值，如 Integer.MAX_VALUE / 2，避免溢出) 如果 i 到 j 没有直接边。在给定的问题中，-1 表示没有直接路径。
-
处理不可达路径：
- 代码中的 mat[i][k] != -1 && mat[k][j] != -1 条件用于检查 i 到 k 和 k 到 j 的路径是否存在。如果任何一段路径不可达（用 -1 表示），则不能通过 k 中转。
- mat[i][j] == -1 条件表示 i 到 j 当前是不可达的，或者之前没有找到任何路径，此时任何通过 k 的有效路径都将是更好的选择。
时间复杂度： Floyd-Warshall算法的时间复杂度为 O(V^3)，其中 V 是图中顶点的数量。这是因为算法有三层嵌套循环，每层循环都遍历所有 V 个顶点。
-
中间节点遍历顺序的灵活性： 虽然 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<Integer> 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算法的基础。
