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

到此就這樣了。上面的注釋是我自己的了解，如果有什麼不對的地方，歡迎大佬們指正。