Network Delay Time
Problem
Network of n nodes; times[i] = [u, v, w] is a directed edge u → v with delay w. Starting from node k, return the time it takes for a signal to reach every node, or −1 if some node is unreachable.
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 22import heapq
def network_delay_time(times, n, k):
adj = {i: [] for i in range(1, n + 1)}
for u, v, w in times:
adj[u].append((v, w))
dist = {i: float('inf') for i in range(1, n + 1)}
dist[k] = 0
pq = [(0, k)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in adj[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (d + w, v))
ans = max(dist.values())
return ans if ans < float('inf') else -1function networkDelayTime(times, n, k) {
const adj = new Map();
for (let i = 1; i <= n; i++) adj.set(i, []);
for (const [u, v, w] of times) adj.get(u).push([v, w]);
const dist = new Array(n + 1).fill(Infinity);
dist[k] = 0;
const pq = [[0, k]];
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]);
const [d, u] = pq.shift();
if (d > dist[u]) continue;
for (const [v, w] of adj.get(u)) {
if (d + w < dist[v]) { dist[v] = d + w; pq.push([d + w, v]); }
}
}
let ans = 0;
for (let i = 1; i <= n; i++) ans = Math.max(ans, dist[i]);
return ans === Infinity ? -1 : ans;
}class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
Map<Integer, List<int[]>> adj = new HashMap<>();
for (int i = 1; i <= n; i++) adj.put(i, new ArrayList<>());
for (int[] e : times) adj.get(e[0]).add(new int[]{e[1], e[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});
while (!pq.isEmpty()) {
int[] top = pq.poll();
int d = top[0], u = top[1];
if (d > dist[u]) continue;
for (int[] nb : adj.get(u)) {
if (d + nb[1] < dist[nb[0]]) {
dist[nb[0]] = d + nb[1];
pq.offer(new int[]{dist[nb[0]], nb[0]});
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = Math.max(ans, dist[i]);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
}class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<pair<int, int>>> adj(n + 1);
for (auto& e : times) adj[e[0]].push_back({e[1], e[2]});
vector<int> dist(n + 1, INT_MAX);
dist[k] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, k});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto& [v, w] : adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, dist[i]);
return ans == INT_MAX ? -1 : ans;
}
};Explanation
A signal spreads through the network along weighted edges, and a node "receives" it as soon as the shortest path from the source reaches it. So we compute the shortest distance from k to every node with Dijkstra's algorithm; the time for the whole network to light up is the largest of those distances.
Dijkstra keeps a dist table (everything starts at infinity except dist[k] = 0) and a min-heap of (distance, node) pairs. We always pop the closest unfinalized node first, which is what makes the algorithm correct for non-negative weights.
When we pop (d, u), the check if d > dist[u]: continue throws away stale heap entries left over from earlier, larger estimates. Otherwise we relax each outgoing edge: if going through u gives a shorter route d + w < dist[v], we update dist[v] and push the new pair.
Example: times = [[2,1,1],[2,3,1],[3,4,1]], source k = 2. The distances become d(1)=1, d(3)=1, d(4)=2, so the answer is max = 2.
At the end we return max(dist.values()), unless some node is still at infinity (unreachable), in which case we return -1.