Floyd-Warshall 全源最短路径算法

前言

全源最短路径是相对单源最短路径而言的，用于查找图中所有点对其它点的最短路径。

Floyd-Warshall算法适用于存在负权重但不存在负回路的图，稠密图，它的运行时间为O(n³)。

它的实质是动态规划。

本文以下图为示例：

最优子结构

具体描述为：对于给定的带权图 G = (V, E)，设 p = <v₁, v₂, …,v_k> 是从 v₁ 到 v_k 的最短路径，那么对于任意 i 和 j，1 ≤ i ≤ j ≤ k，p_ij = <v_i, v_i+1, …, v_j> 为 p 中顶点 v_i 到 v_j 的子路径，那么 p_ij 是顶点 v_i 到 v_j 的最短路径。

设带权图 G = (V, E) 中的所有顶点 V = {1, 2, . . . , n}，考虑一个顶点子集 {1, 2, . . . , k}。对于任意对顶点 i, j，考虑从顶点 i 到 j 的所有路径的中间顶点都来自该子集 {1, 2, . . . , k}，设 p 是该子集中的最短路径。Floyd-Warshall 算法描述了 p 与 i, j 间最短路径及中间顶点集合 {1, 2, . . . , k - 1} 的关系，该关系依赖于 k 是否是路径 p 上的一个中间顶点。

设d^(k)_ij为从结点i到结点j的所有中间结点全部取自于集合 {1, 2, . . . , k} 的一条最短路径的权重。当k=0时，即最短路径中不包含任何中间结点，此时的最短路径就是权重本身值。

具体实现

根据上文分析，可以遍历k值，将最短路径分成两段，如果p_ik和p_kj之和少于p_ij，则认为k是ij最短路径上的中间节点，更新最短路径值。

  public void floydWashall(MatrixEdge[][] edges){
    int n = edges.length;
    int[][] d = new int[n][n];
    
    for (int i = 0; i < d.length; i++) {
        for (int j = 0; j < d.length; j++) {
            if (edges[i][j] != null) {
                d[i][j] = edges[i][j].weight;
            }else {
                if (i == j) {
                    d[i][j] = 0;
                }else {
                    d[i][j] = 10000;
                }
            }
        }
    }
    
    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[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.print(d[i][j] + "   ");
        }
        System.out.println();
    }
}