# Network Delay Time
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/network-delay-time)
Canonical: https://scaleengineer.com/dsa/problems/network-delay-time
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Heap (Priority Queue), Graph
**Companies:** [Netflix](https://scaleengineer.com/companies/netflix), [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
You are given a network of `n` nodes, labeled from `1` to `n`. You are also given `times`, a list of travel times as directed edges `times[i] = (ui, vi, wi)`, where `ui` is the source node, `vi` is the target node, and `wi` is the time it takes for a signal to travel from source to target.

We will send a signal from a given node `k`. Return _the **minimum** time it takes for all the_ `n` _nodes to receive the signal_. If it is impossible for all the `n` nodes to receive the signal, return `-1`.

**Example 1:**

![](https://assets.glich.co/dsa/network-delay-time/image0.png) 

**Input:** times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
**Output:** 2

**Example 2:**

**Input:** times = [[1,2,1]], n = 2, k = 1
**Output:** 1

**Example 3:**

**Input:** times = [[1,2,1]], n = 2, k = 2
**Output:** -1

**Constraints:**

* `1 <= k <= n <= 100`
* `1 <= times.length <= 6000`
* `times[i].length == 3`
* `1 <= ui, vi <= n`
* `ui != vi`
* `0 <= wi <= 100`
* All the pairs `(ui, vi)` are **unique**. (i.e., no multiple edges.)

# Approaches
## Bellman-Ford Algorithm
This approach uses the Bellman-Ford algorithm to find the shortest paths from the source node `k` to all other nodes. Bellman-Ford is capable of handling graphs with negative edge weights, although this problem has only non-negative weights. It works by iteratively relaxing edges, which involves repeatedly checking and updating shortest path estimates until they converge.
**Time:** O(n * E), where `n` is the number of nodes and `E` is the number of edges. The outer loop runs `n-1` times, and the inner loop iterates through all `E` edges. · **Space:** O(n) to store the `dist` array.
**Pros:** Relatively simple to implement.; Can handle negative edge weights (though not needed for this problem).
**Cons:** Less efficient than Dijkstra's algorithm for graphs with non-negative weights.; For the given constraints, it's the slowest approach.
### Explanation
The Bellman-Ford algorithm computes single-source shortest paths in a weighted directed graph. First, we initialize a distance array `dist` of size `n+1` with infinity for all nodes, except for the source node `k`, which is set to 0. The algorithm then relaxes all edges `(u, v)` with weight `w` for `n-1` times. A relaxation step checks if the path to `v` can be shortened by going through `u`. If `dist[u] + w < dist[v]`, we update `dist[v]` to `dist[u] + w`. After `n-1` iterations, the `dist` array will contain the shortest path distances from `k` to all other nodes, provided there are no negative-weight cycles (which is true here). Finally, we find the maximum distance in the `dist` array among all reachable nodes. If any distance is still infinity, it means that node is unreachable, and we should return -1. The result is the maximum finite distance found.

```java
import java.util.Arrays;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;

        for (int i = 0; i < n - 1; i++) {
            boolean updated = false;
            for (int[] edge : times) {
                int u = edge[0];
                int v = edge[1];
                int w = edge[2];
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    updated = true;
                }
            }
            // Optimization: if no distances were updated in an iteration, we can stop early.
            if (!updated) {
                break;
            }
        }

        int maxWait = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                return -1;
            }
            maxWait = Math.max(maxWait, dist[i]);
        }

        return maxWait;
    }
}
```
### Algorithm
- Initialize a distance array `dist` of size `n+1` with a large value (infinity) to store the shortest travel times from `k`.
- Set `dist[k] = 0`.
- Repeat `n-1` times:
  - For each edge `(u, v)` with weight `w` in `times`:
    - If `dist[u]` is not infinity and `dist[u] + w < dist[v]`, update `dist[v] = dist[u] + w`.
- After the loops, find the maximum value in the `dist` array (from `dist[1]` to `dist[n]`). Let this be `max_dist`.
- If `max_dist` is infinity, it means at least one node is unreachable. Return -1.
- Otherwise, return `max_dist`.

## Dijkstra's Algorithm with Priority Queue (Min-Heap)
This is the standard and widely-used implementation of Dijkstra's algorithm. It finds the shortest paths from a source node to all other nodes in a weighted graph with non-negative edge weights. It uses a priority queue (min-heap) to efficiently select the next node to visit based on the current shortest known distance.
**Time:** O(E log n), where `E` is the number of edges and `n` is the number of nodes. Each vertex is added to the priority queue once. Each edge relaxation might add an element to the priority queue, leading to at most `E` insertions. Both poll and offer operations on the priority queue take O(log n) time. · **Space:** O(n + E) for the adjacency list, the distance array, and the priority queue. In the worst case, the priority queue can hold `E` elements.
**Pros:** Generally very efficient for sparse graphs.; A standard and well-understood algorithm for shortest paths.
**Cons:** Slightly more complex to implement than the simple array-based version.; For dense graphs, where `E` is close to `n^2`, its performance can be worse than the O(n^2) implementation. For this problem's specific constraints, it's slightly slower than the array-based version.
### Explanation
The algorithm maintains a set of visited nodes and a priority queue of nodes to visit. The priority queue stores pairs of `(distance, node)` and is ordered by distance. First, we build an adjacency list representation of the graph. We initialize a `dist` array with infinity for all nodes and 0 for the source node `k`. We add `(0, k)` to the priority queue. While the priority queue is not empty, we extract the node `u` with the smallest distance. If `u` has already been processed with a shorter or equal path, we skip it. Otherwise, for each neighbor `v` of `u`, we calculate the new potential distance through `u`. If `dist[u] + weight(u, v) < dist[v]`, we update `dist[v]` and add the new pair `(dist[v], v)` to the priority queue. The algorithm terminates when the priority queue is empty. Finally, we find the maximum distance in the `dist` array. If any node is unreachable (distance is infinity), we return -1. Otherwise, we return the maximum distance.

```java
import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> adj = new HashMap<>();
        for (int[] time : times) {
            adj.computeIfAbsent(time[0], key -> new ArrayList<>()).add(new int[]{time[1], time[2]});
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, k}); // {distance, node}

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int d = current[0];
            int u = current[1];

            if (d > dist[u]) {
                continue;
            }

            if (adj.containsKey(u)) {
                for (int[] edge : adj.get(u)) {
                    int v = edge[0];
                    int w = edge[1];
                    if (dist[u] + w < dist[v]) {
                        dist[v] = dist[u] + w;
                        pq.offer(new int[]{dist[v], v});
                    }
                }
            }
        }

        int maxWait = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                return -1;
            }
            maxWait = Math.max(maxWait, dist[i]);
        }

        return maxWait;
    }
}
```
### Algorithm
- Build an adjacency list `adj` where `adj[u]` contains pairs of `(v, w)` for each neighbor `v` of `u` with edge weight `w`.
- Initialize a distance array `dist` of size `n+1` with infinity, and set `dist[k] = 0`.
- Create a priority queue `pq` and add the starting node `k` with distance 0, i.e., `pq.add({0, k})`.
- While `pq` is not empty:
  - Extract the node `u` with the minimum distance from `pq`.
  - If the extracted distance is greater than `dist[u]`, continue (this is an outdated entry).
  - For each neighbor `v` of `u` with edge weight `w`:
    - If `dist[u] + w < dist[v]`:
      - Update `dist[v] = dist[u] + w`.
      - Add `{dist[v], v}` to `pq`.
- After the loop, find the maximum value in `dist` (from `dist[1]` to `dist[n]`).
- If the maximum value is infinity, return -1.
- Otherwise, return the maximum value.

## Dijkstra's Algorithm with Simple Array
This approach implements Dijkstra's algorithm without an optimized priority queue. Instead of a min-heap, it uses a simple array and a linear scan to find the unvisited node with the minimum distance in each iteration. This is surprisingly effective for dense graphs or graphs with a small number of vertices, as is the case with this problem's constraints.
**Time:** O(n^2 + E). The outer loop runs `n` times. Inside, finding the minimum distance node takes O(n) time. This gives O(n^2). The edge relaxations happen over the course of the algorithm for all `E` edges in total. So the total complexity is dominated by O(n^2). · **Space:** O(n + E) for the adjacency list, distance array, and visited array.
**Pros:** Very efficient for dense graphs where `E` is close to `n^2`.; For the given problem constraints (n <= 100), this O(n^2) approach is the most efficient.; Implementation is straightforward without requiring a Priority Queue data structure.
**Cons:** Inefficient for sparse graphs where `E` is much smaller than `n^2`.
### Explanation
This version of Dijkstra's algorithm is conceptually similar to the priority queue version but differs in how it selects the next node to process. We start by building an adjacency list for the graph. We maintain a `dist` array, initialized to infinity for all nodes except the source `k` (which is 0), and a boolean array `visited` to keep track of processed nodes. The main loop runs `n` times. In each iteration, we scan through all `n` nodes to find the unvisited node `u` with the smallest distance in the `dist` array. Once `u` is found, we mark it as visited. Then, we relax all the edges starting from `u`. For each neighbor `v` of `u`, if we can find a shorter path to `v` via `u`, we update `dist[v]`. After the main loop finishes, the `dist` array contains the shortest path distances. The final result is the maximum distance in the `dist` array, or -1 if any node is unreachable.

```java
import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] time : times) {
            adj.get(time[0]).add(new int[]{time[1], time[2]});
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        boolean[] visited = new boolean[n + 1];
        dist[k] = 0;

        for (int i = 0; i < n; i++) {
            int u = -1;
            int min_dist = Integer.MAX_VALUE;
            // Find the unvisited node with the smallest distance
            for (int j = 1; j <= n; j++) {
                if (!visited[j] && dist[j] < min_dist) {
                    min_dist = dist[j];
                    u = j;
                }
            }

            // If no reachable unvisited node is found
            if (u == -1) break;

            visited[u] = true;

            // Relax edges
            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                int w = edge[1];
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }

        int maxWait = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                return -1;
            }
            maxWait = Math.max(maxWait, dist[i]);
        }

        return maxWait;
    }
}
```
### Algorithm
- Build an adjacency list `adj` for the graph.
- Initialize a distance array `dist` of size `n+1` with infinity, and set `dist[k] = 0`.
- Initialize a boolean array `visited` of size `n+1` to `false`.
- Repeat `n` times:
  - Find the unvisited node `u` with the minimum `dist` value by scanning all nodes. If no such node can be found (all remaining nodes have infinite distance), break the loop.
  - Mark `u` as visited: `visited[u] = true`.
  - For each neighbor `v` of `u` with edge weight `w`:
    - If `!visited[v]` and `dist[u] + w < dist[v]`:
      - Update `dist[v] = dist[u] + w`.
- After the loop, find the maximum value in `dist` (from `dist[1]` to `dist[n]`).
- If the maximum value is infinity, return -1.
- Otherwise, return the maximum value.

# Solutions
### Java

```java
class Solution {
private
  static final int N = 110;
private
  static final int INF = 0x3f3f;
public
  int networkDelayTime(int[][] times, int n, int k) {
    int[][] g = new int[N][N];
    for (int i = 0; i < N; ++i) {
      Arrays.fill(g[i], INF);
    }
    for (int[] e : times) {
      g[e[0]][e[1]] = e[2];
    }
    int[] dist = new int[N];
    Arrays.fill(dist, INF);
    dist[k] = 0;
    boolean[] vis = new boolean[N];
    for (int i = 0; i < n; ++i) {
      int t = -1;
      for (int j = 1; j <= n; ++j) {
        if (!vis[j] && (t == -1 || dist[t] > dist[j])) {
          t = j;
        }
      }
      vis[t] = true;
      for (int j = 1; j <= n; ++j) {
        dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
      }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      ans = Math.max(ans, dist[i]);
    }
    return ans == INF ? -1 : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  const int inf = 0x3f3f;
  int networkDelayTime(vector<vector<int>> &times, int n, int k) {
    vector<vector<int>> g(n, vector<int>(n, inf));
    for (auto &t : times)
      g[t[0] - 1][t[1] - 1] = t[2];
    vector<bool> vis(n);
    vector<int> dist(n, inf);
    dist[k - 1] = 0;
    for (int i = 0; i < n; ++i) {
      int t = -1;
      for (int j = 0; j < n; ++j) {
        if (!vis[j] && (t == -1 || dist[t] > dist[j])) {
          t = j;
        }
      }
      vis[t] = true;
      for (int j = 0; j < n; ++j) {
        dist[j] = min(dist[j], dist[t] + g[t][j]);
      }
    }
    int ans = *max_element(dist.begin(), dist.end());
    return ans == inf ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: INF = 0x3F3F g = defaultdict(list) for u, v, w in times: g[u - 1]. append((v - 1, w)) dist = [INF] * n dist[k - 1] = 0 q = [(0, k - 1)] while q: _, u = heappop(q) for v, w in g[u]: if dist[v] > dist[u] + w: dist[v] = dist[u] + w heappush(q, (dist[v], v)) ans = max(dist) return - 1 if ans == INF else ans

```