Java实现之迪杰斯特拉(Dijkstra)算法

系统管理员 2024-04-01 18:48 90阅读 0赞

## 一.问题引入 ##

### 1.问题引入 ###

![480284d146864c7b804b3a11e4ad1d68.png][]

1)战争时期，胜利乡有7个村庄(A,B,C,D,E,F,G)，现在有六个邮差，从G点出发，需要分别  
把邮件分别送到A, B,C,D,E,F六个村庄

2)各个村庄的距离用边线表示(权)，比如A-B距离5公里

3)问:如何计算出G村庄到其它各个村庄的最短距离?

4)如果从其它点出发到各个点的最短距离又是多少?

## 二.迪杰斯特拉(Dijkstra)算法 ##

### 1.基本介绍 ###

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

### 2.算法过程 ###

迪杰斯特拉(Dijkstra)算法主要步骤

1.  变量g表示邻接矩阵存储的带权图G，S =\{v0\}，将v0到其余顶点的路径长度初始化为权值，即dis\[i\] = matrix\[v0\]\[i\]
2.  找出当前最短距离dis\[k\] = Min(dis\[i\] | vi ∈V - S)，则vk为当前求出的下一条从vo出发的最短路径的终点，将vk纳入S，并从V一S中删除
3.  更新从v0出发到集合V - S中顶点v;的最短路径的长度:如果在S中存在vk;使得dis\[k\] +matrix\[k\]\[i\]<dist\[i\](新间接距离<直接距离/当前间接距离)，则将dis\[i\]修改为新间接距离
4.  重复②、③步骤n-1次，即可按最短路径长度的递增顺序，逐个求出v,到图中其它每个顶点的最短路径

![5066f95d9fd846878c2869f446aaf56b.png][]

### 3.代码实现 ###

public class Dijkstra {
        public static final int N = 65535;
    
        public static void main(String[] args) {
            char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
            //邻接矩阵
            int[][] matrix = new int[vertex.length][vertex.length];
            matrix[0] = new int[]{N, 5, 7, N, N, N, 2};
            matrix[1] = new int[]{5, N, N, 9, N, N, 3};
            matrix[2] = new int[]{7, N, N, N, 8, N, N};
            matrix[3] = new int[]{N, 9, N, N, N, 4, N};
            matrix[4] = new int[]{N, N, 8, N, N, 5, 4};
            matrix[5] = new int[]{N, N, N, 4, 5, N, 6};
            matrix[6] = new int[]{2, 3, N, N, 4, 6, N};
            //创建Graph对象
            Graph graph = new Graph(vertex, matrix);
            graph.showGraph();
            graph.dijkstra(6);
    
    
        }
    }
    
    class Graph {
        char[] vertex;  //保存结点的数据
        int[][] matrix; //存放边,就是邻接矩阵
        VisitedVertex visitedVertex; //已经访问的顶点的集合
    
        public Graph(char[] vertex, int[][] matrix) {
            this.vertex = vertex;
            this.matrix = matrix;
        }
    
        //显示邻接矩阵
        public void showGraph() {
            for (int i = 0; i < vertex.length; i++) {
                for (int j = 1; j < vertex.length; j++) {
                    System.out.printf("%-8d", matrix[i][j]);
                }
                System.out.println();
            }
        }
    
        //迪杰斯特拉算法
        //index 表示出发顶点对应的下标
        public void dijkstra(int index) {
            visitedVertex = new VisitedVertex(vertex.length, index);
            update(index);
            for(int i=0;i<vertex.length;i++){
                index= visitedVertex.getNextIndex(); //访问并返回新的访问节点
                update(index);
            }
            visitedVertex.show();
    
    
    
        }
    
        //更新index下标顶点到周围顶点的前驱顶点,
        public void update(int index) {
            //根据遍历邻接矩阵的matrix[index]行
            int len;
            for (int i = 0; i < matrix[index].length; i++) {
                if(matrix[index][i]==Dijkstra.N)
                    continue;
                len = visitedVertex.getDistance(index) + matrix[index][i];
                if (!visitedVertex.isVisted(i) && len < visitedVertex.getDistance(i)) {
                    visitedVertex.updateDistance(i, len);  //更新出发顶点到i顶点的距离
                    visitedVertex.updatePre(i, index);     //更新i顶点的前驱为index
    
                }
            }
        }
    }
    
    //已访问项点集合
    class VisitedVertex {
        //记录各个顶点是否访问过 true表示访问过, false未访问,会动态更新
        public boolean[] isVisted;
        //每个下标对应的值为前一个顶点下标,会动态更新
        public int[] pre_visited;
        //记录出发顶点到其他所有顶点的距离,比如G为出发顶点,就会记录G到其它顶点的距离,会动态更新,求的最短距离就会存放到dis
        public int[] distance;
    
        //构造器
    
        /**
         * @param length 顶点的个数
         * @param index  出发顶点对应的下标
         */
        public VisitedVertex(int length, int index) {
            this.isVisted = new boolean[length];
            this.pre_visited = new int[length];
            this.distance = new int[length];
            this.isVisted[index] = true;
            //初始化dis数组
            Arrays.fill(distance, Dijkstra.N);
            this.distance[index] = 0;   //出发顶点的访问距离为0
    
        }
    
        //判断下标为index顶点是否访问过
        public boolean isVisted(int index) {
            return isVisted[index];
        }
    
        //更新出发顶点到index顶点的距离
        public void updateDistance(int index, int length) {
            distance[index] = length;
    
        }
        //更新pre这个顶点为index的前驱顶点
    
        /**
         * @param pre   当前节点的前驱节点
         * @param index 当前结点
         */
        public void updatePre(int index, int pre) {
            pre_visited[index] = pre;
    
        }
    
        //返回出发顶点到index顶点的距离
        public int getDistance(int index) {
            return distance[index];
        }
    
        //继续选择并选择新的访问顶点
        public int getNextIndex() {
            int min = Dijkstra.N, index = 0;
            for (int i = 0; i < isVisted.length; i++) {
                if (!isVisted[i] && distance[i] < min) {
                    min = distance[i];
                    index = i;
    
                }
    
    
            }
            //更新index为已经访问过的
            isVisted[index] = true;
            return index;
    
        }
        public void show(){
            //输出isVisited数组
            System.out.println(Arrays.toString(isVisted));
            //输出pre_visited数组
            System.out.println(Arrays.toString(pre_visited));
            //输出distance数组
            System.out.println(Arrays.toString(distance));
        }
    }

打印结果:

> \[true, true, true, true, true, true, true\]  
> \[6, 6, 0, 5, 6, 6, 0\]  
> \[2, 3, 9, 10, 4, 6, 0\]

[480284d146864c7b804b3a11e4ad1d68.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bf8a02e375944e878e08a28cee58b55b.png
[5066f95d9fd846878c2869f446aaf56b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c1177c2312e641798a3a202be680d927.png