推薦資料

推薦學(xué)習(xí)文章

代碼

public class Main {    //不能設(shè)置為Integer.MAX_VALUE，否則兩個Integer.MAX_VALUE相加會溢出導(dǎo)致出現(xiàn)負權(quán)    public static int MaxValue = 10000;    public static void main(String[] args) {        //創(chuàng)建頂點和邊        char[] data = {'A','B','C','D','E','F','G'};        int[][] matrix = {                {10000,5,7,10000,10000,10000,2},                {5,10000,10000,9,10000, 10000,3},                {7,10000,10000,10000,8,10000,10000},                {10000,9,10000,10000,10000,4,10000},                {10000,10000,8,10006,10000,5,4},                {10000,10000,10000,4,5,10000,6},                {2,3,10000,10000,4,6,10000}};        //創(chuàng)建圖        MGraph mGraph = new MGraph(data.length);        mGraph.createGraph(data,matrix);        //頂點數(shù)        int vertex = data.length;        //得到邊的數(shù)目        int edge = getEdgesNum(mGraph);        //調(diào)用dijstra算法計算最短路徑        dijstra1(mGraph, 0);    }    //傳入一個圖，根據(jù)其鄰接矩陣，得到其邊的數(shù)目    public static int getEdgesNum(MGraph mGraph){        if (mGraph.vertexNum == 0){            return -1;        }        int edgeNum = 0;        for (int i = 0;i < mGraph.vertexNum;i++){            for(int j = i + 1;j < mGraph.vertexNum;j++){                if (mGraph.weight[i][j] != 10000){                    //說明這是一條邊，i和j分別是其端點                    edgeNum++;                }            }        }        return edgeNum;    }        public static void dijstra1(MGraph mGraph,int startIndex){        //創(chuàng)建記錄點是否訪問過的數(shù)組        int[] isVisited = new int[mGraph.vertexNum];        //創(chuàng)建記錄startIndex到各個點的最短距離的數(shù)組        int[] shortedDis = new int[mGraph.vertexNum];        //創(chuàng)建記錄startIndex到各個點的路徑的數(shù)據(jù)        String[] paths = new String[mGraph.vertexNum];        //初始化startIndex        isVisited[startIndex] = 1;//已被訪問        shortedDis[startIndex] = 0;//自己到自己的距離為0        //初始化paths        for (int i = 0;i < mGraph.vertexNum;i++){            paths[i] = startIndex + " -> " + i;        }        //記錄最小距離        int minDis = 10000;        //記錄最小距離對應(yīng)的點        int minDisIndex = -1;        //開始，一共搞mGraph.vertexNum - 1次（startIndex自身要去掉）        for (int i = 1;i < mGraph.vertexNum;i++){            minDis = 10000;//!!! 每一次循環(huán)，都要刷新minDis            minDisIndex = -1;            //遍歷每個 沒被訪問過的點，直到找到startIndex到該點距離最小的 點            for (int j = 0;j < mGraph.vertexNum;j++){                if (isVisited[j] == 0 && mGraph.weight[startIndex][j] < minDis){//如果該點沒被訪問過，且startIndex到該點的距離比minDis小                    minDis = mGraph.weight[startIndex][j];                    minDisIndex = j;                }            }                        //for循環(huán)完后，就找到了此點            shortedDis[minDisIndex] = minDis;            isVisited[minDisIndex] = 1;            //然后以此點為中間點，找此點的下一個點，其到startIndex的距離比從startIndex直達下一個點的距離要短            //!!! 更新從index跳到其它節(jié)點的較短路徑。注意，是較短路徑            for (int k = 0;k < mGraph.vertexNum;k++){                if (isVisited[k] == 0 && (minDis + mGraph.weight[minDisIndex][k] < mGraph.weight[startIndex][k])){                    mGraph.weight[startIndex][k] = minDis + mGraph.weight[minDisIndex][k];                    paths[k] = paths[minDisIndex] + " -> " + k;                }            }        }        //最后 打印結(jié)果，看最短路徑        for (int i = 0;i < mGraph.vertexNum;i++){            if (shortedDis[i] == 10000){                System.out.println("不可達");            }else {                System.out.println(startIndex + " 到 " + i + " 的最短路徑是："+paths[i]+" 最短距離是："+ shortedDis[i]);                /**                 * 0到1的最短路徑為：0->1，最短距離是：5                 * 0到2的最短路徑為：0->2，最短距離是：7                 * 0到3的最短路徑為：0->6->5->3，最短距離是：12                 * 0到4的最短路徑為：0->6->4，最短距離是：6                 * 0到5的最短路徑為：0->6->5，最短距離是：8                 * 0到6的最短路徑為：0->6，最短距離是：2                 */            }        }    }        //和上面的dijstra1是一樣的    public static void dijstra(int[][] matrix, int source) {        //最短路徑長度        int[] shortest = new int[matrix.length];        //判斷該點的最短路徑是否求出        int[] visited = new int[matrix.length];        //存儲輸出路徑        String[] path = new String[matrix.length];        //初始化輸出路徑        for (int i = 0; i < matrix.length; i++) {            path[i] = new String(source + "->" + i);        }        //初始化源節(jié)點        shortest[source] = 0;        visited[source] = 1;        for (int i = 1; i < matrix.length; i++) {            int min = 10000;            int index = -1;            for (int j = 0; j < matrix.length; j++) {                //已經(jīng)求出最短路徑的節(jié)點不需要再加入計算并判斷加入節(jié)點后是否存在更短路徑                if (visited[j] == 0 && matrix[source][j] < min) {                    min = matrix[source][j];                    index = j;                }            }            //更新最短路徑            shortest[index] = min;            visited[index] = 1;            //更新從index跳到其它節(jié)點的較短路徑            for (int m = 0; m < matrix.length; m++) {                if (visited[m] == 0 && matrix[source][index] + matrix[index][m] < matrix[source][m]) {                    matrix[source][m] = matrix[source][index] + matrix[index][m];                    path[m] = path[index] + "->" + m;                }            }        }        //打印最短路徑        for (int i = 0; i < matrix.length; i++) {            if (i != source) {                if (shortest[i] == MaxValue) {                    System.out.println(source + "到" + i + "不可達");                } else {                    System.out.println(source + "到" + i + "的最短路徑為：" + path[i] + "，最短距離是：" + shortest[i]);                }            }        }    }}//這是圖class MGraph{    //節(jié)點數(shù)目    int vertexNum;    //節(jié)點    char[] data;    //邊的權(quán)值    int[][] weight;    MGraph(int vertexNum){        this.vertexNum = vertexNum;        data = new char[vertexNum];        weight = new int[vertexNum][vertexNum];    }    //圖的創(chuàng)建    public void createGraph(char[] mData,int[][] mWeight){        if (vertexNum == 0){            return;//節(jié)點數(shù)目為0 無法創(chuàng)建        }        for (int i = 0;i < data.length;i++){            data[i] = mData[i];        }        for (int i = 0;i < mWeight.length;i++){            for (int j = 0;j < mWeight.length;j++){                weight[i][j] = mWeight[i][j];            }        }    }    //打印圖    public void showGraph(){        if (vertexNum == 0){            return;        }        for (int[] oneLine: weight){            for (int oneNum: oneLine){                System.out.printf("%20d",oneNum);            }            System.out.println();        }    }}

結(jié)果

0 到 0 的最短路徑是：0 -> 0 最短距離是：00 到 1 的最短路徑是：0 -> 1 最短距離是：50 到 2 的最短路徑是：0 -> 2 最短距離是：70 到 3 的最短路徑是：0 -> 6 -> 5 -> 3 最短距離是：120 到 4 的最短路徑是：0 -> 6 -> 4 最短距離是：60 到 5 的最短路徑是：0 -> 6 -> 5 最短距離是：80 到 6 的最短路徑是：0 -> 6 最短距離是：2