floyd-warshall 算法用于计算图中所有顶点对之间的最短路径。其核心在于通过迭代地考虑每个顶点作为中间节点来优化路径。本文将深入探讨该算法的正确实现方式，重点分析循环顺序对算法“状态”更新的决定性影响，并提供 java 示例代码，帮助读者避免常见的实现错误。
Floyd-Warshall 算法概述
Floyd-Warshall 算法是一种动态规划算法，用于解决所有顶点对最短路径问题。它通过逐步考虑所有可能的中间顶点来更新任意两个顶点之间的最短路径。算法的核心思想是：对于图中的任意两个顶点 i 和 j，它们之间的最短路径要么不经过某个特定的中间顶点 k，要么经过 k。如果经过 k，则路径长度为 i 到 k 的最短路径加上 k 到 j 的最短路径。这个过程会迭代地对所有顶点 k 进行，最终得到所有顶点对之间的最短路径。
该算法通常使用一个二维矩阵 mat 来存储顶点之间的最短距离。初始时，mat[i][j] 存储的是直接从 i 到 j 的边权，如果不存在直接边，则为无穷大（或一个特殊值如 -1）。
循环顺序的关键性：为什么 k 必须在外层？
Floyd-Warshall 算法的典型实现包含三个嵌套循环，分别遍历中间顶点 k、起始顶点 i 和终止顶点 j。这三个循环的顺序对于算法的正确性至关重要。
考虑以下一种常见的错误实现方式，其中中间顶点 k 的循环位于最内层：
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) {
// 确保路径存在且当前路径更短
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 循环在最内层时，对于每一对 (i, j)，算法会尝试通过所有的 k 来更新 mat[i][j]。然而，在计算 mat[i][k] + mat[k][j] 时，mat[i][k] 和 mat[k][j] 的值可能尚未被充分优化。换句话说，当尝试通过当前 k 更新 (i, j) 的路径时，i 到 k 或 k 到 j 的路径可能还没有考虑到所有编号小于 k 的中间节点进行优化，导致计算结果不准确。它隐式地假设 mat[i][k] 和 mat[k][j] 已经是最短路径，但实际上并非如此。
正确的循环顺序是将中间顶点 k 的循环放在最外层：
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] 检查是否发现更短路径
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 时，我们已经保证了对于所有 p < k 的中间顶点，mat[i][p] 和 mat[p][j] （以及所有其他路径）都已经被优化过了。这样，当计算 mat[i][k] + mat[k][j] 时，mat[i][k] 和 mat[k][j] 已经是考虑了所有编号小于 k 的中间顶点后的最短路径。通过这种方式，算法能够逐步、增量地构建出所有顶点对之间的最短路径，确保每一步的更新都是基于已知的最优子结构。
算法细节与注意事项
-
初始化矩阵：
- mat[i][i] 应初始化为 0。
- 如果 i 到 j 有直接边，mat[i][j] 初始化为边权。
- 如果 i 到 j 没有直接边，mat[i][j] 初始化为表示无穷大（例如 Integer.MAX_VALUE 或题目中使用的 -1）。在代码中，-1 被用作不可达的标记，因此在比较和计算时需要特别处理。
-
路径更新条件：if (mat[i][k] != -1 && mat[k][j] != -1 && (mat[i][j] == -1 || mat[i][j] > mat[i][k] + mat[k][j]))
- mat[i][k] != -1 && mat[k][j] != -1：这确保了从 i 到 k 和从 k 到 j 的路径都是可达的。如果其中任何一段不可达，则无法通过 k 形成新的路径。
- mat[i][j] == -1：如果 i 到 j 之前是不可达的，那么通过 k 找到任何一条路径都意味着找到了一个更短（或第一个）路径。
- mat[i][j] > mat[i][k] + mat[k][j]：如果 i 到 j 已经有路径，则只有当通过 k 形成的路径更短时才进行更新。
-
中间节点遍历顺序的灵活性： 虽然 k 必须是外层循环，但中间节点的具体遍历顺序（例如 0, 1, ..., N-1）本身并不影响算法的最终正确性。只要所有节点都被作为中间节点考虑过，最终结果就是正确的。例如，可以随机打乱节点的顺序进行遍历，算法依然有效：
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); // 获取当前作为中间节点的 k 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 的中间节点的路径都已优化，算法就能正确工作。
总结
Floyd-Warshall 算法以其简洁的结构和解决所有顶点对最短路径问题的能力而闻名。其时间复杂度为 O(V³)，其中 V 是图中顶点的数量。理解其核心的动态规划思想，特别是中间顶点 k 循环必须置于最外层的原理，是正确实现该算法的关键。这个顺序保证了在每次迭代中，我们都基于已经优化的子路径来构建更长的最短路径，从而避免了对未充分优化状态的错误假设。遵循这一原则，可以确保算法高效且准确地计算出图中所有顶点对之间的最短路径。
