Dijkstra 最简单易懂的解释【附java代码】

分手后的思念是犯贱 2022-03-28 11:08 139阅读 0赞

胡扯：这个问题，来自leetcode上面的一个题。两天前已经解答出来了，但是由于乱七八糟的事情，还没有来得及做一个总结。好吧，一个算法竟然前后这么几天才完结。真的是。。。

你可以先去 [百度百科][Link 1] 看看一下这个算法的定义。

下面将一步步诱导你写出这个算法。

**1、大佬级别人物，直接看下面这个图。就可以写出这个算法的。**

![20190110141528234.gif][]

**2、听一个视频讲解上面gif所表达的意思，再来写出这个算法。（我就是听了讲解之后做出来的）**

**[https://video.tudou.com/v/XMTc5MjQ3NTQwOA==.html?spm=a2hzp.8253869.0.0][https_video.tudou.com_v_XMTc5MjQ3NTQwOA_.html_spm_a2hzp.8253869.0.0]**

**3、当你感觉写出来了差不多的时候，你可以去 leetcode 尝试一下这个题 **

[https://leetcode-cn.com/problems/network-delay-time/comments/][https_leetcode-cn.com_problems_network-delay-time_comments]

**4、简单说一下其中要注意的几个点。**

**    **4-1：循环的次数，等于 全部节点的个数。

4-2：问题就是每次选取的是那个节点。视频中已经指出了。每次选择 路径（权值）最小的点。（已经选过的点，不再选取）

4-3：再说一下leetcode这个题。你可以理解成，把水倒入一个迷宫，水蔓延到全部点所需的时间。这样你就会发现，这是要我们求出 最长的那个时间了。 我们使用Dijkstra求出，起始点到每个点的距离，然后找到最大的返回就好了。

**java代码。  个人感觉代码不是很复杂，比较好理解   （为了方便，这里分开给出方法，和测试代码）**

方法：

//寻找最短路径方法   start 是起始点 N 节点个数
        static void Dijkstra(int[][] arr,int N,int start){
            Map<Integer,Integer> map = new HashMap<>();         //用来存放每次循环后的新状态
            Set<Integer> set = new HashSet<>();                  //用来存放已经遍历过的节点
            int minValue = 1000000000;
            // -1 表示走不通
            map.put(start,0);
            while (N > 0){
                set.add(start);
                for (int i = 0;i < arr.length; i++){
                    if ( start == arr[i][0] ){
                        if ( !map.containsKey( arr[i][1] ) ){  // 还没有遍历过这个点
                            map.put(arr[i][1],map.get(start)+arr[i][2]);
                        }
                        else if (  (map.get(arr[i][1])  == -1 ) ||  ( map.get(start)+arr[i][2] < map.get(arr[i][1]) )  ){    //如果遍历过，就看看那种走法更好
                            map.put(arr[i][1],map.get(start)+arr[i][2]);
                        }
                    } else if( !map.containsKey( arr[i][1] ) ){      //判断这个点是否已经遍历过了
                        //没有遍历 给它一个  -1
                        map.put( arr[i][1],-1 );
                    }
                }
                // 找到路径最短的那个节点  下次从他开始遍历  并且这个节点不能是已经遍历过的
                for (Integer i : map.keySet()){
                    if ( set.contains(i) )
                        continue;
                    // -1 表示无穷大
                    if (map.get(i) < minValue && map.get(i) != -1){
                        minValue = map.get(i);
                        start = i;
                    }
                }
                minValue = 1000000000;
                N--;
            }
            //  打印
            for (Integer i : map.keySet()){
                System.out.println( i + " : " + map.get(i) );
            }
        }

测试代码：

public static void main(String[] args) {
    
    //        int[][] arr = { {1,2,1},{2,3,2},{1,3,2} };
    //        Dijkstra(arr,3,1);
    
    //        int[][] arr = { {1,2,7},{1,3,9},{1,6,14},{2,4,15},{3,4,11},{3,6,2},{4,5,6},{6,5,9} };
    //        Dijkstra(arr,6,1);
    
    //        int[][] arr = { {4,2,76},{1,3,79},{3,1,81},{4,3,30},{2,1,47},
    //        {1,5,61},{1,4,99},{3,4,68},{3,5,46},{4,1,6},{5,4,7},
    //        {5,3,44},{4,5,19},{2,3,13},{3,2,18},{1,2,0},{5,1,25},{2,5,58},{2,4,77},{5,2,74} };
    //        Dijkstra(arr,5,3);
    
    //        int[][] arr =  { {1,2,1},{2,3,7},{1,3,4},{2,1,2} };
    //        Dijkstra(arr,4,1);
    
            int[][] arr =  { {1,2,1} };
            Dijkstra(arr,2,2);
    
        }

[Link 1]: https://baike.baidu.com/item/%E8%BF%AA%E6%9D%B0%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95/4049057?fr=aladdin
[20190110141528234.gif]: /images/20220328/3f94e3f252bc4c888992ce39938137e6.png
[https_video.tudou.com_v_XMTc5MjQ3NTQwOA_.html_spm_a2hzp.8253869.0.0]: https://video.tudou.com/v/XMTc5MjQ3NTQwOA==.html?spm=a2hzp.8253869.0.0
[https_leetcode-cn.com_problems_network-delay-time_comments]: https://leetcode-cn.com/problems/network-delay-time/comments/