经典Dijkstra + 优先队列优化Dijkstra + 经典Bellman-Ford
solution 1 \u7ECF\u5178Dijkstra\njava\n    public int networkDelayTime(int[][] times, int N, int K) {\n        int maxValue=6005;\n        int[][] graph = new i
**solution 1 \u7ECF\u5178Dijkstra**\n```java\n    public int networkDelayTime(int[][] times, int N, int K) {\n        int maxValue=6005;\n        int[][] graph = new int[N+1][N+1];\n        for(int i=0;i<graph.length;i++){\n            for(int j=0;j<graph[i].length;j++){\n                 graph[i][j]=maxValue;\n            }\n        }\n        int[] distance=new int[N+1];\n        for(int i=1;i<distance.length;i++){\n            distance[i]=maxValue;\n        }\n        \n        for(int i=0;i<times.length;i++){\n            int src=times[i][0];\n            int des=times[i][1];\n            int time=times[i][2];\n            graph[src][des]=time;\n        }\n        \n          \n        for(int i=1;i<graph[K].length;i++){\n            distance[i]=graph[K][i];\n        }\n        distance[K]=0;\n        boolean[] visited=new boolean[N+1];\n        visited[K]=true;\n \n        for(int i=1;i<=N;i++){\n            int minValue=Integer.MAX_VALUE;\n            int node=-1;\n            for(int j=1;j<distance.length;j++){\n                if(visited[j]==true) continue;\n                if(distance[j]<minValue){\n                    minValue=distance[j];\n                    node=j;\n                }\n            }\n            if(node==-1) break;\n            else visited[node]=true;\n            for(int k=1;k<graph[node].length;k++){\n                if(visited[k]==true) continue;\n                if(distance[k]>distance[node]+graph[node][k]){\n                    distance[k]=distance[node]+graph[node][k];\n                }\n            }\n            \n        }\n        \n        int res=0;\n        for(int i=1;i<distance.length;i++){\n            res=Math.max(res,distance[i]);\n        }\n        return res==maxValue ? -1 : res;\n    }\n```\n\n**solution 2 \u4F18\u5148\u961F\u5217\u4F18\u5316Dijkstra**\n```java\nclass Node{\n        int node;\n        int distance;\n        public Node(int node,int distance){\n            this.node=node;\n            this.distance=distance;\n        }\n    }\n    \n    class NodeComparator implements Comparator<Node>{\n        @Override\n        public int compare(Node o1,Node o2){\n            return o1.distance-o2.distance;\n        }\n    }\n    \n    public int networkDelayTime(int[][] times, int N, int K) {\n        int maxValue=6005;\n        int[][] graph = new int[N+1][N+1];\n        for(int i=0;i<graph.length;i++){\n            for(int j=0;j<graph[i].length;j++){\n                 graph[i][j]=maxValue;\n            }\n        }\n        int[] distance=new int[N+1];\n        for(int i=1;i<distance.length;i++){\n            distance[i]=maxValue;\n        }\n        \n        for(int i=0;i<times.length;i++){\n            int src=times[i][0];\n            int des=times[i][1];\n            int time=times[i][2];\n            graph[src][des]=time;\n        }\n        \n        distance[K]=0;\n        boolean[] visited=new boolean[N+1];\n\n        Queue<Node> priorityQueue = new PriorityQueue<Node>(new NodeComparator());\n        priorityQueue.offer(new Node(K,0));\n        while(!priorityQueue.isEmpty()){\n            Node curNode = priorityQueue.poll();\n            visited[curNode.node]=true;\n            for(int i=1;i<graph[curNode.node].length;i++){\n                if(visited[i]==true) continue;\n                else{\n                    if(distance[i] > distance[curNode.node]+graph[curNode.node][i]){\n                        distance[i]=distance[curNode.node]+graph[curNode.node][i];\n                        priorityQueue.offer(new Node(i,distance[i]));\n                    }\n                }\n            }\n        }\n        \n        int res=0;\n        for(int i=1;i<distance.length;i++){\n            res=Math.max(res,distance[i]);\n        }\n        return res==maxValue ? -1 : res;\n    }\n```\n\n**\u7ECF\u5178Bellman-Ford**\n```java\npublic int networkDelayTime(int[][] times, int N, int K) {\n        int maxValue = 6005;\n        int[] distance = new int[N+1];\n        for(int i=1;i<distance.length;i++){\n            distance[i]=maxValue;\n        }\n        distance[K]=0;\n        for(int j=1;j<N;j++){\n            for(int i=0;i<times.length;i++){\n                int u=times[i][0],v=times[i][1],w=times[i][2];\n            i   f(distance[v] > distance[u]+w ){\n                    distance[v]=distance[u]+w;\n                }\n            }\n        }\n\n        \n        int res=0;\n        for(int i=1;i<distance.length;i++){\n            res=Math.max(res,distance[i]);\n        }\n        return res==maxValue ? -1 : res;\n    }\n```
['Java']