迪杰斯特拉算法求图的某个顶点到其他顶点的最短路径问题

迪杰斯特拉算法：使用图的广度优先遍历算法，比如先从G点出发，找到能与G直接连接的顶点，然后才从与G最近的A出发，找到与A相邻的节点。通过比较G到每个顶点的距离大小，筛选出到每个点的最短路径
代码：

/**
 * 迪杰斯特拉算法球最短路径问题
 */
public class Dijkstra {
    public static void main(String[] args) {
        char[] vertexs = {'A','B','C','D','E','F','G'};
        final int N = 65535;//N表示两点之间不直连
        //邻接矩阵
        int[][] weight = {
                {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},
        };

        Graph graph = new Graph(vertexs, weight);
        graph.print();
        graph.dijkstra(6);
        graph.show();
    }
}

//图
class Graph{
   private char[] vertexs;//顶点数组
   private  int[][] weight;//邻接矩阵
   private VisitedVertex vv;

    public Graph(char[] vertexs, int[][] weight) {
        this.vertexs = vertexs;
        this.weight = weight;
    }

    public void print(){
        for(int[] link:weight){
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * 迪杰斯特拉算法
     * @param index  初始节点
     */
    public void dijkstra(int index){
        vv = new VisitedVertex(vertexs.length,index);
        update(index);
        for(int j = 1;j<vertexs.length;j++){//初始节点已经处理过了，所以需要处理vetexs.length - 1 次
            index = vv.updateArray();
            update(index);
        }
    }

    //输出结果
    public void show(){
        vv.show();
    }

    //更新index下标顶点到周围顶点的距离和前驱节点
    private void update(int index){
        int len = 0;
        //根据遍历我们邻接矩阵的 weight[index]行
        for(int j = 0;j<weight[index].length;j++){
        //这个距离是：初始顶点到index这个点的距离+index点的相邻节点的距离
        //比如index为A点，就是遍历A点的相邻节点
        //但是G到这个节点的距离就是GA的距离加上A到这个节点的距离
            len = vv.getDis(index)+weight[index][j];
            //如果j没有被访问过，并且len小于出发顶点到j点的距离，就要更新
            if(!vv.visited(j) && len<vv.getDis(j)){
               vv.updatePre(index,j);//更新j的前驱节点为index
               vv.updateDis(j,len);//更新初始节点到j的距离为len
            }
        }
    }

}

class VisitedVertex{
    public int[] already_arr;//记录每个顶点是否访问过
    public int[] per_visited;//每个顶点对应的前驱节点的下标数组
    public int[] dis;//记录出发顶点到其他所有顶点的距离，如G为出发点，则会记录G到其他顶点的距离

    //构造器
    /**
     *
     * @param length 顶点的个数
     * @param index  出发顶点对应的下标
     */
    public VisitedVertex(int length,int index){
        this.already_arr = new int[length];
        this.per_visited = new int[length];
        this.dis = new int[length];
        //将初始节点设置为以访问
        this.already_arr[index] = 1;
        //初始化dis
        Arrays.fill(dis,65535);
        this.dis[index] = 0;//设置出发顶点到其他顶点的距离65535，到自己为0
    }

    //判断传入的节点是否访问过
    public boolean visited(int index){
        return already_arr[index] == 1;
    }

    /**
     * 更新出发顶点到index顶点的距离
     * @param index
     * @param len  距离
     */
    public void updateDis(int index,int len){
        dis[index] = len;
    }

    /**
     * 更新pre顶点的前驱节点为index
     * @param index
     * @param pre
     */
    public void updatePre(int index,int pre){
       per_visited[pre] = index;
    }

    /**
     * 返回出发顶点到index顶点的距离
     * @param index
     */
    public int getDis(int index){
        return dis[index];
    }

    /**
     * 继续选择并返回新的访问节点，例如G结束以后，就是处理A节点,因为A离G最近
     * @return
     */
    public int updateArray(){
        int min = 65536;
        int index = 0;
        for(int i = 0;i<already_arr.length;i++){
            if(already_arr[i] == 0 && dis[i]<min){
                min = dis[i];
                index = i;
            }
        }
        //将index设置为以访问
        already_arr[index] = 1;
        return index;
    }

    //显示最后的结果，即输出三个数组
    public void show(){
        System.out.println("===============================================================");
        for(int i :already_arr){
            System.out.print(i+" ");
        }
        System.out.println();
        System.out.println("===============================================================");

        for(int i:per_visited){
            System.out.print(i+" ");
        }
        System.out.println();
        System.out.println("===============================================================");

        for(int i:dis){
            System.out.print(i+" ");
        }
    }
}