最短路径 Floyd 算法

最短路径：对于带权的图来说，最短路径，是指两个顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。

核心思路：以所有的顶点为跳板，看看任意两个的顶点之间有无更短的路径，如果有则更新最短路径，最终得到的结果就是所有任意两个顶点之间的最短路径。

应用：多个源点到其余各顶点的最短路径问题。

应用实例：

image.png

无向图，如上图，求解各顶点之间最短路径。实现如下：

/**
 * 求多源最短路径的算法。 时间复杂度O(n^3)
 */
public class Floyd {
    public static final int I = 100;
    /**
     *           v0
     *        /  |   \
     *    (2)/  |(1)  \(5)
     *      /    |     \
     *    v1-----v2------v3
     *        (4)    (3)
     *
     */
    //邻接距阵 （代表顶点到顶点之间最短路径权值和的矩阵）
    public static int[][] d = new int[][]{
            {0, 2, 1, 5},
            {2, 0, 4, I},
            {1, 4, 0, 3},
            {5, I, 3, 0}
    };
    // p 代表 对应顶点最小路径的前驱矩阵
    public static int[][] p=new int[][]{
            {0,1,2,3},
            {0,1,2,3},
            {0,1,2,3},
            {0,1,2,3}
    };
    public static void floyd(){
        //第一层遍历： 分别以v0 v1 v2....v(d.length-1) 为跳板，计算所有路径权重的最小值
        for (int k = 0; k < d.length; k++) {
            //第二层遍历： 以确定的跳板为基础，遍历所有的行
            for (int i = 0; i < d.length; i++) {
                //第三层遍历：以确定的跳板为基础，遍历所有的列
                for (int j = 0; j < d.length; j++) {
                    //如果发现以跳板为基础的路径值更小，则更新d的值
                    if(d[i][j] > d[i][k] + d[k][j]){
                        d[i][j] = d[i][k] + d[k][j];
                        /**
                         *  记录一下路径：d[i][j]的值因跳板k而发生了变化:
                         *  (i, j) 的路径变成了   从(i，k)，然后再从(k, j)。
                         *  所以前驱节点应该是 k, 但是假如（i, k）中间还有跳板,
                         *  即vi 到 vk 之间最短的路径 是经过了其他的节点的情况。
                         *  此时（i，j）的前驱节点，应该是（i，k）的前驱节点
                         */
                        p[i][j] = p[i][k];
                    }
                }
            }
        }
    }

    /**
     * 打印路径
     */
    public static void printShortPath(){
        for (int i = 0; i < d.length; i++) {
            for (int j = 0; j < d.length; j++) {
                System.out.print("v" + i + "->v" + j + "  weight: " + d[i][j]);
                System.out.print("  path: " + "v" + i);
                int k =p[i][j]; //取出 (i, j)的前驱节点:k
                while (k != j){ //还有前驱节点
                    System.out.print("->" + "v" + k);
                    k = p[k][j];  //从前驱节点vk 开始，到vj 之间看还有没有前驱节点（跳板）
                }
                System.out.println("->" + "v" + k);
            }
        }
    }


    @Test
    public void test(){
        floyd();
        printShortPath();
    }
}

输出结果：

v0->v0  weight: 0  path: v0->v0
v0->v1  weight: 2  path: v0->v1
v0->v2  weight: 1  path: v0->v2
v0->v3  weight: 4  path: v0->v2->v3
v1->v0  weight: 2  path: v1->v0
v1->v1  weight: 0  path: v1->v1
v1->v2  weight: 3  path: v1->v0->v2
v1->v3  weight: 6  path: v1->v0->v2->v3
v2->v0  weight: 1  path: v2->v0
v2->v1  weight: 3  path: v2->v0->v1
v2->v2  weight: 0  path: v2->v2
v2->v3  weight: 3  path: v2->v3
v3->v0  weight: 4  path: v3->v2->v0
v3->v1  weight: 6  path: v3->v2->v0->v1
v3->v2  weight: 3  path: v3->v2
v3->v3  weight: 0  path: v3->v3