我的Floyd Warshall算法为何出错？循环顺序影响结果的困惑

题目 #

Implementing Floyd Warshall（来自GeeksforGeeks）

我的思路 #

原本想让每个节点都有机会成为任意顶点对i和j的中间节点，以此计算最短路径。

错误代码 #

class Solution{
    public void shortest_distance(int[][] mat){
        int N = mat.length;
        
        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];
                    }
                }
            }
        }
    }
}

测试用例问题 #

输入 #

12
0 4 2 1 2 9 4 8 -1 4 -1 -1
9 0 3 6 2 6 2 3 6 -1 -1 3
7 1 0 10 8 9 1 3 -1 7 -1 10
5 1 9 0 3 -1 1 10 7 1 -1 7
-1 5 1 4 0 2 10 4 10 6 4 5
7 8 3 7 5 0 5 1 3 5 7 2
6 -1 6 1 10 7 0 10 -1 -1 7 7
-1 3 2 7 4 -1 4 0 10 5 6 10
10 6 1 10 4 4 7 10 0 4 7 4
1 1 6 8 8 9 2 10 6 0 -1 3
5 9 3 -1 4 3 -1 -1 -1 3 0 1
2 2 8 6 2 4 4 3 -1 3 4 0

我的输出 #

0 2 2 1 2 4 2 5 7 2 6 5
5 0 3 3 2 4 2 3 6 4 6 3
6 1 0 2 3 5 1 3 7 3 7 4
2 1 4 0 3 5 1 4 7 1 7 4
6 2 1 3 0 2 2 3 5 4 4 4
4 4 3 5 4 0 4 1 3 5 6 2
3 2 5 1 4 6 0 5 8 2 7 5
6 3 2 4 4 6 3 0 9 5 6 6
5 2 1 3 4 4 2 4 0 4 7 4
1 1 3 2 3 5 2 4 6 0 7 3
3 3 3 4 3 3 4 4 6 3 0 1
2 2 3 3 2 4 4 3 7 3 4 0

预期输出 #

0 2 2 1 2 4 2 5 7 2 6 5
5 0 3 3 2 4 2 3 6 4 6 3
4 1 0 2 3 5 1 3 7 3 7 4
2 1 4 0 3 5 1 4 7 1 7 4
5 2 1 3 0 2 2 3 5 4 4 4
4 4 3 5 4 0 4 1 3 5 6 2
3 2 5 1 4 6 0 5 8 2 7 5
6 3 2 4 4 6 3 0 9 5 6 6
5 2 1 3 4 4 2 4 0 4 7 4
1 1 3 2 3 5 2 4 6 0 7 3
3 3 3 4 3 3 4 4 6 3 0 1
2 2 3 3 2 4 4 3 7 3 4 0

问题核心 #

发现把k循环移到最外层后代码就能正常运行，想不通当前循环顺序出错的原因。

问题解答 #

Floyd-Warshall算法的核心逻辑是逐步允许使用前k个节点作为中间节点来更新最短路径，所以k必须放在最外层循环。

你的循环顺序是i→j→k，这意味着对于每一对(i,j)，你尝试用所有节点k作为中间节点更新路径，但这里的问题在于：当你更新mat[i][j]时，可能还没有计算出i到k或者k到j的最优路径——因为i和j的循环在k前面，你无法利用那些经过其他中间节点优化后的路径。

举个例子，假设存在路径i→m→k→j，当k循环到当前节点时，i→m→k的最短路径可能还没被计算出来（因为m可能在后面的i或j循环里才会被处理），导致你只能得到i→k→j的直接路径，而无法得到更短的i→m→k→j。

而正确的k→i→j顺序，是先固定中间节点集合{0,1,...,k}，然后对所有i,j对，检查是否通过k作为中间节点能得到更短的路径。这样每一轮k循环后，所有经过前k个节点的最短路径都被正确更新，后续的循环可以基于这些已经优化过的路径继续计算，保证了所有可能的中间节点组合都被考虑到。

比如你测试用例中第3行第1列的结果，正确值是4，你的代码算成6——这就是因为你的循环顺序没让中间节点的优化路径被及时利用，导致没找到更短的路径。

内容的提问来源于stack exchange，提问作者Vivek