图——Folyd算法——多源最短路径，可以解决负权值问题

最新推荐文章于 2024-09-09 18:28:37 发布

热干面的日常学习

最新推荐文章于 2024-09-09 18:28:37 发布

阅读量2k

点赞数

分类专栏：数据结构与算法学习文章标签：数据结构

本文链接：https://blog.csdn.net/Cxf2018/article/details/109527251

版权

数据结构与算法学习专栏收录该内容

28 篇文章

订阅专栏

该算法的主要思想是：利用动态绘规划的思想寻找给定的加权图中多源点之间的最短路径。每一次找到更小的路径都会更新在方阵中。

package graph.FloydAlgorithm;

public class Floyd {
    public static void main(String[] args) {
        int[][] matrix =  {
                {0,-1,3,-1},
                {2,0,-1,-1},
                {-1,7,0,1},
                {6,-1,-1,0}
        };
        System.out.println("实现算法之前：");
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                System.out.print(matrix[i][j]+" ");
            }
            System.out.println();
        }
        floyd(matrix);

        System.out.println("实现算法之后：");
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                System.out.print(matrix[i][j]+" ");
            }
            System.out.println();
        }
    }

    public static void floyd(int[][] matrix){
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                for (int k = 0; k < matrix.length; k++) {
                    if(matrix[j][i]!=-1&&matrix[i][k]!=-1){
                        if(matrix[j][k]>matrix[j][i]+matrix[i][k]||matrix[j][k]==-1){
                            matrix[j][k] = matrix[j][i]+matrix[i][k];
                        }
                    }

                }
            }
        }
    }
}

Floyd算法与Dijkstra算法的不同

Floyd算法是求任意两点之间的距离，是多源最短路，而Dijkstra(迪杰斯特拉)算法是求一个顶点到其他所有顶点的最短路径，是单源最短路。
Floyd算法属于动态规划，我们在写核心代码时候就是相当于推dp状态方程，Dijkstra(迪杰斯特拉)算法属于贪心算法。
Dijkstra(迪杰斯特拉)算法时间复杂度一般是o(n²),Floyd算法时间复杂度是o(n³),Dijkstra(迪杰斯特拉)算法比Floyd算法块。
Floyd算法可以算带负权的，而Dijkstra(迪杰斯特拉)算法是不可以算带负权的。并且Floyd算法不能算负权回路。