floyd算法解析

floyd算法可求得多源点间的最短路径
算法使用动态规划求解：

for(int k=0;k<n;k++){
// 计算最大中间点下标为k的源点间的最短路径
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            path[i][j]=Math.min(path[i][k]+path[k][j],path[i][j]);
        }
    }
}

状态转移方程

dp[i][j][k]=min(dp[i][j[k-1]],dp[k-1][i][k]+dp[k-1][j][k]);
其中 k 表示 i 与 j 之间最大中间点的下标

这个算法是怎么推导的？

// 1）可求得所有中间点下标最大为0的源点间最短路径
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            path[i][j]=Math.min(path[i][0]+path[0][j],path[i][j]);
        }
    }
// 2）在1）的基础上可求得所有中间点下标最大为1的源点间最短路径
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            path[i][j]=Math.min(path[i][1]+path[1][j],path[i][j]);
        }
    }
// 3）在2）的基础上可求得所有中间点下标最大为2的源点间最短路径
for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            path[i][j]=Math.min(path[i][2]+path[2][j],path[i][j]);
        }
    }
// ...
// k）在k-1）的基础上可求得所有中间点下标最大为k的源点间最短路径
// 假设两个源点x与y：x与y是连通的并且x与y间最短路径上的最大中间点下标为k
// 则: 在执行完这一步后，求出的path[x][y]即为x源点到y源点的最短路径
for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            path[i][j]=Math.min(path[i][k]+path[k][j],path[i][j]);
        }
    }