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

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

    

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

 

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

 

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

https://video.tudou.com/v/XMTc5MjQ3NTQwOA==.html?spm=a2hzp.8253869.0.0

 

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

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

    }