最短路径[dijkstra算法]——视频讲解+JAVA实现

dijkstra算法逻辑：

想要理解floyd算法的实现逻辑，最形象的视频讲解是很有必要的。

这里小编极力推荐B站蓝不过海呀这个Up的视频讲解，讲的非常细节，

比自己去看一些什么算法导论效率要高的多，毕竟相较于文字，

人对图形化的东西更有印象。

B站连接：【图-最短路径-Dijkstra(迪杰斯特拉)算法】

视频中只是对算法的逻辑进行了讲解，但是没有涉及代码的实现，接下来，

我会依照视频讲解逻辑，补充一个JAVA代码的实现方式，文章末尾附带源码。

代码实现：

视频中是基于这样一个表格进行算法实现的：

如果放在代码里，可以抽离出三个数组来进行管理：

如下我们就来具体实现一下这个算法：

首先初始化所有数组：

初始化完毕，就可以遍历下面这个表了，要遍历n次，n是总节点数，从第一列开始遍历：

所以我们要建立一个for循环：

每一列的遍历（每一次循环），我们都要去找当前到那个节点路径长度是最短的，接下来寻找当前还没有确定的顶点中，谁最短：

接下来，通过最小顶点indexMin，去寻找其周围的最短路径：

到了这里，此算法就已经实现了，只需要循环更新n列即可。

---

源码：

  /**
     * 迪杰斯特拉算法，求最短路径
     * 缺点：不能是负权值
     *
     * @param vSrc  给定始顶点
     * @param dist  储存顶点的路径长度
     * @param pPath 储存路径，按照并查集的逻辑
     *              <p>
     *              事先说明我自己定义的图的储存方式：
     *              char[] ArrayV;//用来存顶点的
     *              int[][] matrix;//用来存对应边的权重的
     *              （了解即可，我们主要聚焦算法的实现）
     */
    public void dijkstra(char vSrc, int[] dist, int[] pPath) {
 
        int n = arrayV.length;//获得节点的长度
 
        boolean[] visited = new boolean[n];//用于标记，visited[i]是否已经确定最短路径,默认为false
 
        Arrays.fill(dist, Integer.MAX_VALUE);//先把存距离的数组初始化成最大值
        Arrays.fill(pPath, -1);//路径初始化为无效值-1（因为路径数组存的都是上一个顶点的下标嘛）
 
        int index = getIndexOfV(vSrc);//此方法可以获得，vSrc在ArrayV数组对应的下标
        dist[index] = 0;//自己到自己的距离就是0
 
//        pPath[index]=0;//这里起始位置对应下标可以设置也可以不设置，不影响最总结果
 
        for (int k = 0; k < n; k++) {//对表遍历n列
            int min=Integer.MAX_VALUE;//把最小值定义成最大值
 
            int indexMin=0;//这个下标用来指向最小值，默认为0
 
            for (int i = 0; i <n ; i++) {
                if(visited[i]==false&&//没有被确定的顶点
               dist[i]<min ){//要找最小的顶点
                    min=dist[i];//更新最小值
                    indexMin=i;//更新下标
                }
            }
            //程序执行到这个，已经找到当前列，中路径最小的顶点
            visited[indexMin]=true;//可以直接确定从起始顶点，到这个顶点的最短路径已经找到
 
 
            /**
             * matrix储存每条边的权重
             * matrix[i][j]==最大值---说明没有边
             * */
            for (int i = 0; i <n ; i++) {
                if(matrix[indexMin][i]!=Integer.MAX_VALUE&&//必须有边
                visited[i]==false&&//必须是没有确定最短路径的顶点
                dist[indexMin]+matrix[indexMin][i]<dist[i]){//新的路径必须小于久的路径，才更新最短路径
 
                    dist[i]=dist[indexMin]+matrix[indexMin][i];//更行长度
                    pPath[i]=indexMin;//更新路径，指向上一个节点indexMin
                }
            }
 
        }
 
 
    }
 

测试如下这个图：

执行结果：