743. Network Delay Time.md

title	toc	date	tags	top
743. Network Delay Time	false	2017-10-30	Leetcode Heap Depth-first Search Breath-first Search Graph	743

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