Floyd算法

算法概述

弗洛伊德算法，是解决任意两点间的最短路径的一种算法。它的时间复杂度为 O(N^3）空间复杂度为 O(N^2)。

算法描述

弗洛伊德算法其实采用的是动态规划

设F(i,j,k)表示节点i到节点j只以(1,k)之间的节点作为中间节点的最短路径，那么

1. 如果最短路径进过k

    F(i,j,k) = F(i,k,k-1) + F(k,j,k-1)
   

2. 如果最短路径不经过k

    F(i,j,k) = F(i,j,k-1)
   

所以最短路径为两者之间的最小值

F(i,j,k) = min[F(i,k,k-1) + F(k,j,k-1), F(i,j,k-1)]

公式看起来很复杂，但是代码写起来很简单

首先，如果任意两个节点之间不允许经过第三个点，那么节点间的最短路径就是初始路径。

现在我们放松条件，允许经过1个节点，例如节点1，那么对于节点i到节点j的最短路径，只需要判断

e[i][1] + e[1][j] < e[i][j]

代码如下

//经过节点1
for(int i =1; i <= n; i++){
    for(int j=1; j<=n; j++){
        if(e[i][1] + e[1][j] < e[i][j]){
            e[i][j] = e[i][1] + e[1][j]
        }
    }
}    

接下来继续求在只允许经过1和2号两个节点的情况下任意两点之间的最短路程。如何做呢？我们需要在只允许经过1号节点时任意两点的最短路程的结果下，再判断如果经过2号节点是否可以使得节点i到节点j之间的路程变得更短。即判断 e[i][2]+e[2][j]是否比 e[i][j]要小

//经过节点2
for(int i =1; i <= n; i++){
    for(int j=1; j<=n; j++){
        if(e[i][2] + e[2][j] < e[i][j]){
            e[i][j] = e[i][1] + e[1][j]
        }
    }
}    

以此类推，最后允许经过所有的节点，即可求出两两节点间的最短路径了

for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(e[i][j]>e[i][k]+e[k][j])
                 e[i][j]=e[i][k]+e[k][j];

这段代码的基本思想就是：最开始只允许经过节点1进行中转，接下来只允许经过节点1和节点2进行中转……允许经过1~n所有节点进行中转，求任意两点之间的最短路程。也就是从节点i到节点j只经过前k号点的最短路程，这样也就对应到上述的公式中了

代码实现

public class Floyd {

    private static final Integer INF = Integer.MAX_VALUE;

    public void floyd(int[][] edge){
        for (int k = 0; k < edge.length; k++){
            for (int i = 0; i < edge.length; i++){
                for (int j = 0; j < edge.length; j++){
                    if (edge[i][k] < INF && edge[k][j] < INF &&
                    edge[i][k] + edge[k][j] < edge[i][j]){
                        edge[i][j] = edge[i][k] + edge[k][j];
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] edge = new int[][]{
                {0,2,6,4},
                {INF,0,3,INF},
                {7,INF,0,1},
                {5,INF,12,0}
        };

        Floyd floyd = new Floyd();
        floyd.floyd(edge);
        for (int i  = 0; i < edge.length; i++){
            System.out.println(Arrays.toString(edge[i]));
        }
    }
}

参考文献

1. Floyd-Warshall算法
2. 只有五行的 Floyd 最短路算法