> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/breadth-first-search/743-network-delay-time.md).

# 743 Network Delay Time

## 743. [Network Delay Time](https://leetcode.com/problems/network-delay-time/description/)

## 1. Question

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:**

1. `N`will be in the range`[1, 100]`.
2. `K`will be in the range`[1, N]`.
3. The length of`times`will be in the range`[1, 6000]`.
4. All edges`times[i] = (u, v, w)`will have`1 <= u, v <= N`and`1 <= w <= 100`.

## 2. Implementation

**(1) BFS**

```java
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**

```java
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堆优化**

```java
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)