Day597&598.迪杰斯特拉算法 -数据结构和算法Java

迪杰斯特拉算法

• 求最短路径（某一个节点到其他节点的最短路径）
• 使用图的广度优先遍历

一、问题引出

二、介绍

三、算法过程

四、代码实现

package com.achang.algorithm;

import java.util.Arrays;

/**
 * 迪杰斯特拉最短距离算法
 */
public class DijkstraAlgorithm {
    public static void main(String[] args) {
        char[] vertex = {'a', 'b', 'c', 'd', 'e', 'f', 'g' };
        final int N = 65535;//不可连接距离
        int[][] matrix = {
                {N, 5, 7, N, N, N, 2},
                {5, N, N, 9, N, N, 3},
                {7, N, N, N, 8, N, N},
                {N, 9, N, N, N, 4, N},
                {N, N, 8, N, N, 5, 4},
                {N, N, N, 4, 5, N, 6},
                {2, 3, N, N, 4, 6, N},
        };
        Graphs graphs = new Graphs(vertex, matrix);
        graphs.list();
        graphs.dsj(6);
        System.out.println("==========如下为结果=========");
        graphs.showResult();
    }

}

class VisitedVertex{
    //记录各个节点是否被访问过 1被访问过 0未访问
    public int[] alreadyArr;
    //每个下标对应的值为前一个节点的下标
    public int[] preVisited;
    //记录触发定点到其他所有节点的距离，比如G为出发节点，就记录了G到其他节点的距离
    public int[] disArr;

    /**
     * @param length 节点的个数
     * @param index 出发节点对应的下标，表示从哪个节点开始，比如G为出发节点，那传入的就是6
     */
    public VisitedVertex(int length,int index){
        this.alreadyArr = new int[length];
        this.preVisited = new int[length];
        this.disArr = new int[length];
        Arrays.fill(disArr,65535);//给数组中的所有元素置为65535
        this.alreadyArr[index] = 1;//设置出发节点已被访问过
        this.disArr[index] = 0;//为出发节点自己与自己的距离为0
    }

    /**
     * 判断index对应下标的节点，是否被访问过
     * @return 访问过返回T，否则为F
     */
    public boolean in(int index){
        return alreadyArr[index] == 1;
    }

    /**
     * 更新出发节点到index节点的距离
     * @param index index节点的下标
     * @param length 距离
     */
    public void updateDis(int index,int length){
        this.disArr[index] = length;
    }

    /**
     * 更新pre节点的前驱节点为index节点
     */
    public void updatePre(int index,int pre){
        this.preVisited[pre] = index;
    }

    /**
     * 返回出发节点到index节点的距离
     */
    public int getDis(int index){
        return disArr[index];
    }

    //继续选择并返回新的访问节点，比如这里的G节点完了后，就是A节点作为新的访问节点
    public int updateArr(){
        int min = 65535,index = 0;
        for (int i = 0; i < alreadyArr.length; i++) {
            if (alreadyArr[i] == 0 && disArr[i] < min){//目前i节点并未被访问过
                //更新
                min = disArr[i];
                index = i;
            }
        }
        //更新index节点已被访问过
        alreadyArr[index] = 1;
        return index;
    }

    //显示最后结果，将三个数组的情况输出
    public void showResult(){
        System.out.println("preVisited："+Arrays.toString(preVisited));
        System.out.println("alreadyArr："+Arrays.toString(alreadyArr));
        System.out.println("disArr："+Arrays.toString(disArr));
    }


}

//图结构
class Graphs {
    private char[] vertex;//节点数组
    private int[][] matrix;//邻接矩阵
    private VisitedVertex vv;

    public Graphs(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    public void list() {
        for (int[] ints : matrix) {
            System.out.println(Arrays.toString(ints));
        }
    }

    public void showResult(){
        vv.showResult();
    }

    /**
     * 迪杰斯特拉算法
     * @param index 表示出发节点对应的下标，如出发节点为G，那就传入G节点的下标
     */
    public void dsj(int index){
        vv = new VisitedVertex(vertex.length, index);
        update(index);//更新index下标节点到周围节点的距离和前驱节点
        for (int i = 1; i < vertex.length; i++) {
            index = vv.updateArr();//选择并返回新的访问节点
            update(index);//更新index下标节点到周围节点的距离和前驱节点
        }
    }

    //更新index下标节点到周围节点的距离和周围节点的前驱节点，
    private void update(int index){
        int len = 0;//表示出发节点到index节点的距离+从index节点到j节点的距离的和
        //根据遍历邻接矩阵的matrix[index]行
        for (int i = 0; i < matrix[index].length; i++) {
            len = vv.getDis(index) + matrix[index][i];
            //如果i节点没有被访问过 && len小于出发节点到i节点的距离，就需要更新
            if (!vv.in(i) && len < vv.getDis(i)){
                vv.updatePre(i,index);//更新i节点的前驱为index节点
                vv.updateDis(i,len);//更新出发节点到i节点的距离
            }
        }
    }
}