美文网首页
图论-最短路径Dijikstra算法(Java)

图论-最短路径Dijikstra算法(Java)

作者: aruba | 来源:发表于2021-08-12 08:44 被阅读0次

    和最小生成树不同的是,最短路径是求顶点A到B之前最短的权,不用考虑中间经过哪些顶点,只要这些路径的总和最小
    Dijikstra算法:初始化一个边集合,指定一个原始点,以该点为中心,求出到当前点到别的顶点的最小权(遍历求最小权,记录另一个顶点),将权更新到边集合中,无法到达的暂时不需要处理,将另一个顶点设为中心,往复操作
    实现代码:

        public static class Dijikstra {
            private int verticeSize;// 顶点数量
            private int[] vertices; // 顶点数组
            private int[][] matrix; // 矩阵
            private static final int MAX = Integer.MAX_VALUE;
    
            public Dijikstra(int verticeSize) {
                this.verticeSize = verticeSize;
                vertices = new int[verticeSize];
                matrix = new int[verticeSize][verticeSize];
            }
    
            public int[] dijikstra() {
                //原始点
                int sourcePoint = 0;
                //最小路径集合
                int[] distances = new int[verticeSize];
    
                //初始化边集合
                for (int i = 0; i < verticeSize; i++) {
                    distances[i] = matrix[sourcePoint][i];
                }
                //用1表示访问了sourcePoint的顶点
                vertices[sourcePoint] = 1;
    
                for (int i = 1; i < verticeSize; i++) {//从第二个点开始遍历
                    //1.查找最短边
                    int minDis = MAX;
                    //和sourcePoint最近的顶点
                    int minPoint = 0;
                    for (int j = 0; j < verticeSize; j++) {
                        if (vertices[j] == 0 && distances[j] < minDis) {
                            minDis = distances[j];
                            minPoint = j;
                        }
                    }
    
                    if (minDis == MAX) {//所有顶点都访问了
                        return distances;
                    }
    
                    //最小边的顶点算访问过了
                    vertices[minPoint] = 1;
                    //2.更新边的集合
                    for (int j = 0; j < verticeSize; j++) {
                        if (vertices[j] == 0 && matrix[minPoint][j] != MAX) {//只要更新没访问过的顶点距离
                            //如果minPoint到j的距离 + minPoint到原始点的最短距离 < 原本原始点到j的最短距离  则更新
                            if (matrix[minPoint][j] + distances[minPoint] < distances[j]) {
                                distances[j] = matrix[minPoint][j] + distances[minPoint];
                            }
                        }
                    }
                }
    
                return distances;
            }
        }
    

    测试代码:


            Dijikstra graph = new Dijikstra(6);
            int[] v0 = new int[]{0, Dijikstra.MAX, 5, 30, Dijikstra.MAX, Dijikstra.MAX};
            int[] v1 = new int[]{2, 0, Dijikstra.MAX, Dijikstra.MAX, Dijikstra.MAX, 8};
            int[] v2 = new int[]{Dijikstra.MAX, 15, 0, Dijikstra.MAX, 7, Dijikstra.MAX};
            int[] v3 = new int[]{Dijikstra.MAX, Dijikstra.MAX, Dijikstra.MAX, 0, Dijikstra.MAX, Dijikstra.MAX};
            int[] v4 = new int[]{Dijikstra.MAX, Dijikstra.MAX, Dijikstra.MAX, Dijikstra.MAX, 0, 18};
            int[] v5 = new int[]{Dijikstra.MAX, Dijikstra.MAX, Dijikstra.MAX, 4, Dijikstra.MAX, 0};
            graph.matrix[0] = v0;
            graph.matrix[1] = v1;
            graph.matrix[2] = v2;
            graph.matrix[3] = v3;
            graph.matrix[4] = v4;
            graph.matrix[5] = v5;
    
            int[] distances = graph.dijikstra();
            for (int i = 0; i < distances.length; i++) {
                System.out.println(i + ":" + distances[i]);
            }
    

    结果:
    0:0
    1:20
    2:5
    3:30
    4:12
    5:28

    相关文章

      网友评论

          本文标题:图论-最短路径Dijikstra算法(Java)

          本文链接:https://www.haomeiwen.com/subject/qgycbltx.html