Leetcode
Heap
Depth-first Search
Breath-first Search
Graph
There are N network nodes, labelled 1 to N.
Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.
Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.
Note:
- N will be in the range [1, 100].
- K will be in the range [1, N].
- The length of times will be in the range [1, 6000].
- All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.
分析¶
这道题目思路是非常直接的。题目都说了有向图directed graph，并且需要求最长的最短路径。那么就是题目就转化为shortest path of directed graph. 由于所有路径都为正数，可以使用经典的Dijkstra's algorithm.
public int networkDelayTime(int[][] times, int N, int K) { int[] distTo = new int[N + 1]; PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2)->o1[1]-o2[1]); Arrays.fill(distTo, Integer.MAX_VALUE); //construct graph Map<Integer, Integer>[] graph = (HashMap<Integer, Integer>[]) new HashMap<?, ?>[N + 1]; for (int i = 1; i < N + 1; i++) graph[i] = new HashMap<>(); for (int[] time : times) graph[time[0]].put(time[1], time[2]); // dijkstra algorithm distTo[K] = 0; pq.offer(new int[]{K, distTo[K]}); while (!pq.isEmpty()) { int v = pq.poll()[0]; Map<Integer, Integer> distFromV = graph[v]; for (int w : distFromV.keySet()) if (distTo[w] > distTo[v] + distFromV.get(w)) { pq.remove(new int[]{w, distTo[w]}); distTo[w] = distTo[v] + distFromV.get(w); pq.offer(new int[]{w, distTo[w]}); } } // find min int maxLength = -1; for (int i = 1; i <= N; i++) if (distTo[i] == Integer.MAX_VALUE) return -1; else if (i != K && distTo[i] > maxLength) maxLength = distTo[i]; return maxLength; }
近期评论