【程序员必会十大算法】之迪杰斯特拉算法_Android小白

推荐资料

推荐学习文章

代码

public class Main {
    //不能设置为Integer.MAX_VALUE，否则两个Integer.MAX_VALUE相加会溢出导致出现负权
    public static int MaxValue = 10000;

    public static void main(String[] args) {
        //创建顶点和边
        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}};
        //创建图
        MGraph mGraph = new MGraph(data.length);
        mGraph.createGraph(data,matrix);

        //顶点数
        int vertex = data.length;
        //得到边的数目
        int edge = getEdgesNum(mGraph);

        //调用dijstra算法计算最短路径
        dijstra1(mGraph, 0);
    }
    //传入一个图，根据其邻接矩阵，得到其边的数目
    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){
        //创建记录点是否访问过的数组
        int[] isVisited = new int[mGraph.vertexNum];
        //创建记录startIndex到各个点的最短距离的数组
        int[] shortedDis = new int[mGraph.vertexNum];
        //创建记录startIndex到各个点的路径的数据
        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;
        //记录最小距离对应的点
        int minDisIndex = -1;

        //开始，一共搞mGraph.vertexNum - 1次（startIndex自身要去掉）
        for (int i = 1;i < mGraph.vertexNum;i++){
            minDis = 10000;//!!! 每一次循环，都要刷新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循环完后，就找到了此点
            shortedDis[minDisIndex] = minDis;
            isVisited[minDisIndex] = 1;

            //然后以此点为中间点，找此点的下一个点，其到startIndex的距离比从startIndex直达下一个点的距离要短
            //!!! 更新从index跳到其它节点的较短路径。注意，是较短路径
            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;
                }
            }
        }

        //最后 打印结果，看最短路径
        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);
        }

        //初始化源节点
        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++) {
                //已经求出最短路径的节点不需要再加入计算并判断加入节点后是否存在更短路径
                if (visited[j] == 0 && matrix[source][j] < min) {
                    min = matrix[source][j];
                    index = j;
                }
            }

            //更新最短路径
            shortest[index] = min;
            visited[index] = 1;

            //更新从index跳到其它节点的较短路径
            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{
    //节点数目
    int vertexNum;
    //节点
    char[] data;
    //边的权值
    int[][] weight;

    MGraph(int vertexNum){
        this.vertexNum = vertexNum;
        data = new char[vertexNum];
        weight = new int[vertexNum][vertexNum];
    }

    //图的创建
    public void createGraph(char[] mData,int[][] mWeight){
        if (vertexNum == 0){
            return;//节点数目为0 无法创建
        }

        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();
        }
    }
}

结果

0 到 0 的最短路径是：0 -> 0 最短距离是：0
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