跳转至

743. Network Delay Time

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