743 Network Delay Time

743. Network Delay Time

1. Question

There areNnetwork nodes, labelled1toN.

Giventimes, a list of travel times as directed edgestimes[i] = (u, v, w), whereuis the source node,vis the target node, andwis the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain nodeK. How long will it take for all nodes to receive the signal? If it is impossible, return-1.

Note:

1. Nwill be in the range[1, 100].

2. Kwill be in the range[1, N].

3. The length oftimeswill be in the range[1, 6000].

4. All edgestimes[i] = (u, v, w)will have1 <= u, v <= Nand1 <= w <= 100.

2. Implementation

(1) BFS

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        int[][] edge = new int[N + 1][N + 1];
        for (int[] e : edge) {
            Arrays.fill(e, Integer.MAX_VALUE);
        }

        for (int[] time : times) {
            edge[time[0]][time[1]] = time[2];
        }



        int[] delay = new int[N + 1];
        Arrays.fill(delay, Integer.MAX_VALUE);
        delay[K] = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(K);

        while (!queue.isEmpty()) {
            int size = queue.size();
            Set<Integer> set = new HashSet<>();

            for (int i = 0; i < size; i++) {
                int curNode = queue.remove();

                for (int nextNode = 1; nextNode <= N; nextNode++) {
                    if (edge[curNode][nextNode] != Integer.MAX_VALUE 
                        && delay[curNode] + edge[curNode][nextNode] < delay[nextNode]) {
                        if (!set.contains(nextNode)) {
                            set.add(nextNode);
                            queue.add(nextNode);
                        }
                        delay[nextNode] = delay[curNode] + edge[curNode][nextNode];
                    }
                }
            }
        }

        int res = 0;
        for (int i = 1; i <= N; i++) {
            res = Math.max(res, delay[i]);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

(2) Dijkstra's Algorithm

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        Map<Integer, List<int[]>> adjList = new HashMap<>();

        for (int[] time : times) {
            adjList.putIfAbsent(time[0], new ArrayList<int[]>());
            adjList.get(time[0]).add(new int[] {time[1], time[2]});
        }

        int[] distance = new int[N + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);

        distance[K] = 0;
        boolean[] visited = new boolean[N + 1];

        while (true) {
            int candNode = -1;
            int candDist = Integer.MAX_VALUE;

            for (int i = 1; i <= N; i++) {
                if (!visited[i] && distance[i] < candDist) {
                    candNode = i;
                    candDist = distance[i];
                }
            }

            if (candNode == -1) {
                break;
            }
            visited[candNode] = true;

            if (adjList.containsKey(candNode)) {
                for (int[] info : adjList.get(candNode)) {
                    int nextNode = info[0];
                    int nextDist = info[1];

                    distance[nextNode] = Math.min(distance[nextNode], nextDist + distance[candNode]);
                }
            }   
        }

        int res = Integer.MIN_VALUE;

        for (int i = 1; i <= N; i++) {
            res = Math.max(res, distance[i]);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

(3) Dijkstra's Algorithm堆优化

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        Map<Integer, List<int[]>> adjList = new HashMap<>();

        for (int[] time : times) {
            adjList.putIfAbsent(time[0], new ArrayList<int[]>());
            adjList.get(time[0]).add(new int[] {time[1], time[2]});
        }

        int[] distance = new int[N + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);

        PriorityQueue<int[]> minHeap = new PriorityQueue<int[]>((info1, info2) -> (info1[1] - info2[1]));
        minHeap.add(new int[] {K, 0});

        while (!minHeap.isEmpty()) {
            int[] info = minHeap.remove();
            int curNode = info[0];
            int curDist = info[1];

            // 最小堆每次都会pop出最小距离的node，如果distance[node]不等于 Integer.MAX_VALUE,说明该node的距起点的最小距离已经更新，所以不再更新
            if (distance[curNode] != Integer.MAX_VALUE) {
                continue;
            }

            distance[curNode] = curDist;
            if (adjList.containsKey(curNode)) {
                for (int[] nextInfo : adjList.get(curNode)) {
                    int nextNode = nextInfo[0];
                    int nextDist = nextInfo[1];

                    if (distance[nextNode] == Integer.MAX_VALUE) {
                        minHeap.add(new int[] {nextNode, curDist + nextDist});
                    }
                }
            }
        }

        int res = Integer.MIN_VALUE;
        for (int i = 1; i <= N; i++) {
            res = Math.max(res, distance[i]);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

3. Time & Space Complexity

BFS: 时间复杂度O(N ^ 2), 空间复杂度O(N ^ 2)

Dijkstra's Algorithm: 时间复杂度O(N ^ 2 + E), E是times的长度，空间复杂度O(N + E)

Dijkstra's Algorithm堆优化: 时间复杂度O(NlogN + E), 空间复杂度O(N + E)