Warshall算法和Floyd算法

• 归属：动态规划

• 名词：

  1. 传递闭包：存在一个有向图，能用布尔邻接矩阵表示（1、0）。存在一个矩阵，它能够给定图的顶点之间是否存在任意长度的有向路径，这种矩阵称为有向图的传递闭包，是我们能够在常数时间内判断第j个顶点是否可从第i个顶点到达。

• 作用：

  1. Warshall算法可以计算一个布尔邻接矩阵的传递闭包。
  2. Floyd算法可以计算加权连通图的每个顶点到其它所有顶点之间的最短距离，使用矩阵表示。

• 思想：

  1. Warshall算法：存在 (a,b)=1 (b,c)=1，则(a,c)=1，以此为基础遍历完整个矩阵，如图。

     
     Wsrshall算法

  2. Floyd算法：若一个点到另外一个点没有路径，则把它的值视为无穷大，这里以10000做代替。

     
     Floyd算法

• 算法：

    /**
     * Warshall算法
     * @param paths 布尔有向图矩阵
     * @param n 几阶矩阵
     * @return 传递闭包
     */
    public static boolean[][] warshall(boolean[][] paths, int n) {
        boolean beforePaths[][] = paths.clone();
        boolean nowPaths[][] = paths.clone();
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    //这里的k代替了c
                    nowPaths[i][j] = beforePaths[i][j] || beforePaths[i][k] && beforePaths[k][j];
                    beforePaths = nowPaths.clone();
                }
            }
        }
        return nowPaths;
    }

    /**
     * Floyd算法
     * @param paths 加权连通图
     * @param n 几阶矩阵
     * @return 表示任意两个点之间的最短路径的距离矩阵
     */
    public static int[][] floyd(int[][] paths, int n) {
        int[][] d = paths.clone();
        for (int k = 0; k < n;k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        return d;
    }