GuilinDev

Lc0743

05 August 2008

743 Network Delay Time

题目

There are 

1

N
network nodes, labelled 
1

1
to 
1

N
.

Given 

1

times
, a list of travel times as directed edges 
1

times[i] = (u, v, w)
, where 
1

u
is the source node, 
1

v
is the target node, and 
1

w
is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node 

1

K
. How long will it take for all nodes to receive the signal? If it is impossible, return 
1

-1
.

Example 1:

1
2

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

Note:

  1. 1

    N
    will be in the range 
    1

    [1, 100]
    .
  2. 1

    K
    will be in the range 
    1

    [1, N]
    .
  3. The length of 
    1

    times
    will be in the range 
    1

    [1, 6000]
    .
  4. All edges 
    1

    times[i] = (u, v, w)
    will have 
    1

    1 <= u, v <= N
    and 
    1

    0 <= w <= 100
    .

分析

根据题目，从一个节点访问所有别的节点，总共需要多长时间。这个是图的BFS或者DFS做法，求从源节点到最远目标节点的最短路径，是Dijkstra类似的问题，Time O(Nlog(N) + E), Space: O(N + E)。

PS另外两种算法：

Floyd–Warshall算法：Time complexity: O(N^3), Space complexity: O(N^2)

Bellman-Ford算法：Time complexity: O(N*E), Space complexity: O(N)

代码

BFS实现Dijkstra，java的API需要熟悉下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>(); //分解二维数组，用一个hashmap来存储源节点和带遍历的目标节点+delay时间
        for (int[] time : times) { // key为源节点，value为map，其中key为目标节点，value为delay时间
            map.putIfAbsent(time[0], new HashMap<>());
            map.get(time[0]).put(time[1], time[2]);
        }
        
        // 用一个优先队列来记录从源节点向外扩散的层，每一层的目标节点根据delay time来确定
        // 目标节点-delay time
        Queue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        
        // 先把参数源节点加入到优先队列，它的delay time是0
        pq.offer(new int[]{K, 0});
        
        // 因为节点是以整数表示，所以用一个数组true/false即可表示是否被访问过
        boolean[] visited = new boolean[N + 1]; //从1开始，免得标记时还需要转换
        
        int result = 0;
        
        // BFS
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int currNode = curr[0];
            int currDelay = curr[1];
            
            if (visited[currNode]) { // 当前节点已被访问过
                continue;
            }
            
            // 标记访问
            visited[currNode] = true;
            
            result = currDelay; //把结果更新为当前层的delay time
            
            // 处理当前层每个节点的下一层
            if (map.containsKey(currNode)) { // 防止null
                for (int neighbor : map.get(currNode).keySet()) { // 获取当前节点的所有目标节点
                    pq.offer(new int[]{neighbor, currDelay + map.get(currNode).get(neighbor)}); // 源节点到当前层delay time + 当前层到目标节点的delay time
                }
            } 
            
            N--; // 层数-1
        }
        return N == 0 ? result : -1;
    }
}
This site is open source. Improve this page.