算法--floyd多源最短路径

floyd多源最短路径：可以解决每个顶点到其他顶点的最短路劲

• 不适用条件：出现负环
• 算法步骤：用二维数组记录顶点到其他顶点的最短路劲，dp[i][j]:表示i顶点到j顶点的最短路劲
  • 初始化：自己到自己为0，其他根据边权进行赋值，无边的为无穷大
  • 进行顶点个数轮数，每轮借助的顶点为k，除k外的其他顶点借助k这个顶点到达其他顶点，选取直通和借路到达两者较小的更新dp[i][j]

/**
 * floyd多源最短路径
 * @param n 顶点个数
 * @param edges 边权集 {{from,to,weight}}
 */
public void floyd(int n,int[][] edges){
    int[][] dp=new int[n][n];
    //初始化：自己到自己（对角线）为0，其他根据边权进行赋值，两顶点无边的为∞
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i!=j){
                dp[i][j]=Integer.MAX_VALUE;
            }
        }
    }
    //例子为无向图：双向赋值
    for (int[] edge : edges) {
        int i = edge[0];
        int j = edge[1];
        dp[i][j]=edge[2];
        dp[j][i]=edge[2];
    }
    //需进行n轮，每轮除k外其他顶点借助k这个顶点到达其他顶点
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i!=j||i!=k) {//自己到自己或自己借助自己都无需进行
                    if (dp[i][k] != Integer.MAX_VALUE && dp[k][j] != Integer.MAX_VALUE) {//路可以连通
                        //直通和借路之间选择较小的
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                    }
                }
            }
        }
    }

}

检查负环：可以在正常进行n轮后，检查对角线是否存在小于0的，若存在，则存在负环。

• 本文作者： zzr
• 本文链接： http://zzruei.github.io/2023/11aa404b0f.html
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！