Dijstra（单源最短路径）

注意：在运用该算法之前你必须得先有一个图。

一、图

图的创建我就......完全是抄袭别人的图了。为了测试效果

package BinaryTreeText;


import java.util.LinkedList;

/**
 * 图的创建-->邻接矩阵
 *
 * */
public class Graph {
    private int vertexSize; //顶点数量

    private  int[] vertexs; // 结点数组（存储每一个结点的编号）

    private int[][] matrix; // 邻接矩阵

     final int MAX_WEIGHT = 1000; // 不能到达的路的权值

    private boolean[] isVisited;

    public int getMAX_WEIGHT() {
        return MAX_WEIGHT;
    }

    public int[][] getMatrix() {
        return matrix;
    }

    public void setMatrix(int[][] matrix) {
        this.matrix = matrix;
    }

    public int getVertexSize() {
        return vertexSize;
    }

    public void setVertexSize(int vertexSize) {
        this.vertexSize = vertexSize;


    }
    public void createGraph(Graph graph){
        int[] a0 = {0,1,5,graph.MAX_WEIGHT,graph.MAX_WEIGHT,11,graph.MAX_WEIGHT,graph.MAX_WEIGHT,graph.MAX_WEIGHT};
        int[] a1 = {1,0,3,7,5,graph.MAX_WEIGHT,graph.MAX_WEIGHT,graph.MAX_WEIGHT,graph.MAX_WEIGHT};
        int[] a2 = {5,3,0,graph.MAX_WEIGHT,1,7,graph.MAX_WEIGHT,graph.MAX_WEIGHT,graph.MAX_WEIGHT};
        int[] a3 = {graph.MAX_WEIGHT,7,graph.MAX_WEIGHT,0,2,graph.MAX_WEIGHT,3,graph.MAX_WEIGHT,graph.MAX_WEIGHT};
        int[] a4 = {graph.MAX_WEIGHT,5,1,2,0,3,6,9,graph.MAX_WEIGHT};
        int[] a5 = {graph.MAX_WEIGHT,graph.MAX_WEIGHT,7,graph.MAX_WEIGHT,3,0,graph.MAX_WEIGHT,5,graph.MAX_WEIGHT};
        int[] a6 = {graph.MAX_WEIGHT,graph.MAX_WEIGHT,graph.MAX_WEIGHT,3,6,graph.MAX_WEIGHT,0,2,7};
        int[] a7 = {graph.MAX_WEIGHT,graph.MAX_WEIGHT,graph.MAX_WEIGHT,graph.MAX_WEIGHT,9,5,2,0,4};
        int[] a8 = {graph.MAX_WEIGHT,12,8,21,graph.MAX_WEIGHT,7,graph.MAX_WEIGHT,4,0};

        matrix[0] = a0;
        matrix[1] = a1;
        matrix[2] = a2;
        matrix[3] = a3;
        matrix[4] = a4;
        matrix[5] = a5;
        matrix[6] = a6;
        matrix[7] = a7;
        matrix[8] = a8;
    }


    public Graph(int vertexSize){
        this.vertexSize = vertexSize;
        this.matrix = new int[vertexSize][vertexSize];
        this.vertexs = new int[vertexSize];
        for (int i = 0;i<vertexSize;i++){
            vertexs[i] = i;            // 表示V0--V4
        }
        isVisited = new boolean[vertexSize];
    }
           

二、算法核心部分

由于我平时看博客的时候会直接看代码，代码上要是有注释的话，就不用来回上下翻动了。所以我就在代码里面注释的很详细了。在此就不在啰嗦。

但是我要声明的是：单源最短路径就是：一个节点到其余各个节点的距离最短，所以我下面有一个shortTablePath【】的数组，专门来存放最短路径。。。注意：刚开始的时候他只是虚拟的最短路径，最后循环完它才是最终的最短路径。

package BinaryTreeText;

public class Dijstra {

        private final static int MAXVEX = 9;
        private final static int MAXWEIGHT = 65535;
        // 用于存储最短路径的数组
        private int shortTablePath[] = new int[MAXVEX];

        /**
         * 获取一个图的最短路径
         *
         * */

        public void shortesPathDijstra(Graph graph){
            // 用来存此路径有没有找到
            boolean isgetPath[] = new boolean[MAXVEX];
            int min ;
            int k = 0 ; // 用来存下标


            // 这个for循环是先自己人为规定一个最短路径，比如说我们选第0号节点所能到达的边的权重为最开始的最短路径
            for (int j = 0;j < graph.getVertexSize(); j++){
                // graph.getMatrix()是得到图的邻接矩阵
                shortTablePath[j] = graph.getMatrix()[0][j];
            }

            // 0号节点到自己的路径肯定是0
            shortTablePath[0] = 0;
            // 0号节点已经确认
            isgetPath[0] = true;

            // 因为0号节点已经确认了，所以我们从1号节点开始
            //两个 for循环相当于遍历图的邻接矩阵
            for (int v = 1; v < graph.getVertexSize();v++){
                 min = MAXWEIGHT;
                 for (int w = 0;w <graph.getVertexSize();w++){
                     // 选择当前权值最小的节点，记录它的下标
                     //如果这个权值等于min或者大于min的话，它肯定不是最小的权值
                     // 还有一点要注意的是，你当前选择的结点必须是还没有被确定下来的结点
                     if (shortTablePath[w]<min && !isgetPath[w]){
                         k = w;
                         min = shortTablePath[w];
                     }

                 }
                 // 内层跑完一趟for（）之后，k就记录的是最小权重的节点编号
                isgetPath[k] = true; //既然我们选出最小的权值了，肯定要标记它已经选好，下次就不用再它了

                // 声明一下，这块容易搞混，这个for循环完全是用来循环的，没有别的意思
                for (int j = 0; j < graph.getVertexSize();j++){
                    //如果这个节点还没选，并且min（shortTablePath里面上一层for循环中选出的最小值）+graph.getMatrix()[k][j]
                    // （第k行，上层for循环选中的最小权值对应的结点编号）< 当前（还没有确定的）最短路径时，我们就可以更新
                    // 虚拟最短路径数组的值了
                    //到最后遍历完整个邻接矩阵，虚拟最短路径就不在虚拟了，2333
                    if (!isgetPath[j] && ( min + graph.getMatrix()[k][j] < shortTablePath[j])){
                        shortTablePath[j] = min + graph.getMatrix()[k][j];
                    }
                }

            }

            for (int i = 0;i<shortTablePath.length;i++){
                System.out.println("V0到"+i+"的最短路径为"+shortTablePath[i]);

            }

        }

    public static void main(String[] args) {
        Graph graph = new Graph(9);
        graph.createGraph(graph);
        new  Dijstra().shortesPathDijstra(graph);


    }


}
           

三、运行结果

V0到V0的最短路径为0

V0到V1的最短路径为1

V0到V2的最短路径为4

V0到V3的最短路径为7

V0到V4的最短路径为5

V0到V5的最短路径为8

V0到V6的最短路径为10

V0到V7的最短路径为12

V0到V8的最短路径为16

到此就这样了。上面的注释是我自己的理解，如果有什么不对的地方，欢迎大佬们指正。