最短路径算法——Dijkstra(迪杰斯特拉)

2017-08-25 本文已影响0人 Mirs

最短路径算法——Dijkstra(迪杰斯特拉)

恩好久没有写博客了，虽然我知道这种算法的博客基本很少有人看，但是我还是决定把他写出来

Dijkstra算法属于最短路径的算法，他的本质就是 一个按照路径长度递增的次序产生的最短路径算法，他的应用还是比较普遍的。

我们这边那这个图来说

image.png

假如说我们这里要寻找从 v0 - v8 的最短路径，我们首先要想Prim算法一样，把图转为邻接矩阵，如图下所示

邻接矩阵

他这个图表示的就是你一个点到另一个点的距离，比如V0到V1是1 到v2是5 到v3是无穷大说明不到3 v4 ,5 ,6,7,8 同样是不通的，v1到v2的距离是3 到v3的距离是7 ，就这样一个规律

这个算法是这样走的

默认一个空的数组就是他的数组的长度(点的数量) 比如是 shortTablePath[],默认的值就是∞，他到所有点的距离都是无穷大，还要初始化一个boolean数组 isgetPath[] 来记录当前的点是不是是最短的路径，同时防止回环。
初始化到第一个点的距离是0 因为v0到v0的距离永远是0（本身到本身）同时把

isgetPath[0]置为true
然后从v0开始循环 v0 到 v1加起来的距离小于shortTablePath[1] 所以v0 -> v1的最短距离就是 1，v0 -> v2 的距离是5，5+0<∞ 所以v0 -> v2 的最短距离就是5，因为后面都不通，所以还是∞，第一遍结束结果就是

shortTablePath = {0 1 5 ∞ ∞ ∞ ∞ ∞ ∞}

isgetPath={true,false,false,false,false,false,false,false}
循环上面的步骤,到v1时

shortTablePath={0 1 4 8 6 1000 1000 1000 1000 }

isgetPath = {true true false false false false false false false }

到V2时：

shortTablePath={0 1 4 8 5 11 1000 1000 1000 }

isgetPath= {true true true false false false false false false }

到V3时

shortTablePath={0 1 4 7 5 8 11 14 1000 }

isgetPath={true true true false true false false false false }

以后的步骤省略。。。

从上面看我们可以大致理解到这个算法的核心

寻找到到V8节点的最短距离， 那么我找到V0到V1  V1到V2  V2到V3 。。。每个节点的最短的距离，那么他们的和就是到V8的最短的距离

我们用代码实现来看先建立了一个Graph类这个类主要是构建图和获取图的一些属性

public class Graph {
    private int vertexSize;//顶点数量

    public int getVertexSize() {
        return vertexSize;
    }


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

    private int [] vertexs;//顶点数组
    private int[][]  matrix;
    public int[][] getMatrix() {
        return matrix;
    }


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

    public static final int MAX_WEIGHT = 1000;
    private boolean [] isVisited;
    public Graph(int vertextSize){
        this.vertexSize = vertextSize;
        matrix = new int[vertextSize][vertextSize];
        vertexs = new int[vertextSize];
        for(int i = 0;i<vertextSize;i++){
            vertexs[i] = i;
        }
        isVisited = new boolean[vertextSize];
    }

    /**
     * 创建图的过程
     */
    public void createGraph(){
        int [] a1 = new int[]{0,1,5,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
        int [] a2 = new int[]{1,0,3,7,5,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
        int [] a3 = new int[]{5,3,0,MAX_WEIGHT,1,7,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
        int [] a4 = new int[]{MAX_WEIGHT,7,MAX_WEIGHT,0,2,MAX_WEIGHT,3,MAX_WEIGHT,MAX_WEIGHT};
        int [] a5 = new int[]{MAX_WEIGHT,5,1,2,0,3,6,9,MAX_WEIGHT};
        int [] a6 = new int[]{MAX_WEIGHT,MAX_WEIGHT,7,MAX_WEIGHT,3,0,MAX_WEIGHT,5,MAX_WEIGHT};
        int [] a7 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,3,6,MAX_WEIGHT,0,2,7};
        int [] a8 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,9,5,2,0,4};
        int [] a9 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,7,4,0};

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

}

核心算法 Dijkstra.java

public class Dijkstra {
    private final static int MAXVEX = 9;
    private final static int MAXWEIGHT = 1000;
    private int shortTablePath[] = new int[MAXVEX]; //记录的是V0到某订单的最短路径

    public void shortestPathDijkstra(Graph graph){
        int min;
        int k = 0;//记录下标
        boolean isgetPath[] = new boolean[MAXVEX];
        
        //初始化shortTablePath
        shortTablePath = graph.getMatrix()[0];
        shortTablePath[0]=0;
        isgetPath[0] = true;

        for (int v = 1 ;v<graph.getVertexSize();v++){
            min = MAXWEIGHT;

           //是否是到当前节点的最短路径
            for (int i = 0; i < graph.getVertexSize() ; i++) {
                if(!isgetPath[i]&&shortTablePath[i]<min){
                    k = i;
                    min = shortTablePath[i];
                }
            }
        
            //标志k的位置当前是最短路径
            isgetPath[k] =true;
        
            // 判断当前节点到各个节点的当前最短路径
            for (int j = 0; j < graph.getVertexSize(); j++) {

                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.print(shortTablePath[i]+"  ");
            }
            System.out.println();
            for (int i = 0; i < isgetPath.length ; i++) {
                System.out.print(isgetPath[i]+"  ");
            }
            System.out.println();
            System.out.println();
            System.out.println();
        }


       //打印到各个节点的最短路径
       for (int i = 0; i < shortTablePath.length; i++) {
            System.out.println("V0到V" + i + "最短路径为 " + shortTablePath[i]);
       }

    }
    
    //打印当期那的邻接矩阵
    public void printGraph(Graph graph){
        for (int i = 0; i < graph.getVertexSize() ; i++) {
            for (int j = 0; j <  graph.getMatrix()[i].length; j++) {
                if(graph.getMatrix()[i][j]<Graph.MAX_WEIGHT) {
                    System.out.print(graph.getMatrix()[i][j] + " ");
                }else {
                    System.out.print("∞" + " ");
                }
            }
            System.out.println();
        }
    }


    public static void main(String[] args) {
        Graph graph = new Graph(MAXVEX);
        graph.createGraph();
        Dijkstra dijkstra = new Dijkstra();
        dijkstra.printGraph(graph);
        dijkstra.shortestPathDijkstra(graph);
    }
}

这个就是Dijkstra算法，跑起来~

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

nice。。。

最短路径算法——Dijkstra(迪杰斯特拉)

最短路径算法——Dijkstra(迪杰斯特拉)

猜你喜欢

热点阅读