Network Delay Time

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

1
2


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

Example 2:

1
2


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

Example 3:

1
2


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

Solution

Method 1 – Dijkstra’s Algorithm (BFS with Priority Queue)

Intuition

Dijkstra’s algorithm is ideal for finding the shortest time to reach all nodes in a weighted directed graph. By always expanding the node with the smallest current time, we ensure the earliest possible signal arrival at each node.

Approach

Build a graph as an adjacency list mapping each node to its neighbors and edge weights.
Use a min-heap (priority queue) to always process the node with the smallest current signal time.
Track visited nodes to avoid revisiting and update the answer with the latest signal time.
If all nodes are visited, return the maximum time; otherwise, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
class Solution {
public:
	int networkDelayTime(vector<vector<int>>& times, int n, int k) {
		vector<vector<pair<int,int>>> g(n+1);
		for (auto& t : times) g[t[0]].emplace_back(t[1], t[2]);
		vector<bool> vis(n+1, false);
		priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
		pq.emplace(0, k);
		int ans = 0, cnt = 0;
		while (!pq.empty()) {
			auto [d, u] = pq.top(); pq.pop();
			if (vis[u]) continue;
			vis[u] = true; ans = d; cnt++;
			for (auto& [v, w] : g[u]) if (!vis[v]) pq.emplace(d+w, v);
		}
		return cnt == n ? ans : -1;
	}
};

 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


import "container/heap"
type Item struct{ dist, node int }
type PQ []Item
func (pq PQ) Len() int { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PQ) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PQ) Push(x interface{}) { *pq = append(*pq, x.(Item)) }
func (pq *PQ) Pop() interface{} { old := *pq; x := old[len(old)-1]; *pq = old[:len(old)-1]; return x }
func networkDelayTime(times [][]int, n int, k int) int {
	g := make([][]struct{to, w int}, n+1)
	for _, t := range times { g[t[0]] = append(g[t[0]], struct{to, w int}{t[1], t[2]}) }
	vis := make([]bool, n+1)
	pq := &PQ{{0, k}}
	heap.Init(pq)
	ans, cnt := 0, 0
	for pq.Len() > 0 {
		cur := heap.Pop(pq).(Item)
		if vis[cur.node] { continue }
		vis[cur.node] = true; ans = cur.dist; cnt++
		for _, e := range g[cur.node] {
			if !vis[e.to] { heap.Push(pq, Item{cur.dist+e.w, e.to}) }
		}
	}
	if cnt == n { return ans }
	return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


import java.util.*;
class Solution {
	public int networkDelayTime(int[][] times, int n, int k) {
		Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
		for (int i = 1; i <= n; i++) graph.put(i, new HashMap<>());
		for (int[] t : times) graph.get(t[0]).put(t[1], t[2]);
		Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
		pq.add(new int[]{0, k});
		boolean[] vis = new boolean[n+1];
		int ans = 0, cnt = 0;
		while (!pq.isEmpty()) {
			int[] cur = pq.poll();
			int d = cur[0], u = cur[1];
			if (vis[u]) continue;
			vis[u] = true; ans = d; cnt++;
			for (var entry : graph.get(u).entrySet()) {
				int v = entry.getKey(), w = entry.getValue();
				if (!vis[v]) pq.add(new int[]{d+w, v});
			}
		}
		return cnt == n ? ans : -1;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


import java.util.*
class Solution {
	fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
		val graph = Array(n+1) { mutableListOf<Pair<Int,Int>>() }
		for (t in times) graph[t[0]].add(t[1] to t[2])
		val vis = BooleanArray(n+1)
		val pq = PriorityQueue(compareBy<Pair<Int,Int>> { it.first })
		pq.add(0 to k)
		var ans = 0; var cnt = 0
		while (pq.isNotEmpty()) {
			val (d, u) = pq.poll()
			if (vis[u]) continue
			vis[u] = true; ans = d; cnt++
			for ((v, w) in graph[u]) if (!vis[v]) pq.add(d+w to v)
		}
		return if (cnt == n) ans else -1
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


import heapq
class Solution:
	def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
		from collections import defaultdict
		g = defaultdict(list)
		for u, v, w in times:
			g[u].append((v, w))
		vis = set()
		pq = [(0, k)]
		ans = 0
		while pq:
			d, u = heapq.heappop(pq)
			if u in vis: continue
			vis.add(u); ans = d
			for v, w in g[u]:
				if v not in vis:
					heapq.heappush(pq, (d+w, v))
		return ans if len(vis) == n else -1

 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


use std::collections::{BinaryHeap, HashMap};
impl Solution {
	pub fn network_delay_time(times: Vec<Vec<i32>>, n: i32, k: i32) -> i32 {
		let mut g: HashMap<i32, Vec<(i32, i32)>> = HashMap::new();
		for t in times.iter() {
			g.entry(t[0]).or_default().push((t[1], t[2]));
		}
		let mut vis = vec![false; (n+1) as usize];
		let mut heap = BinaryHeap::new();
		heap.push((0, k));
		let mut ans = 0; let mut cnt = 0;
		while let Some((neg_d, u)) = heap.pop() {
			let d = -neg_d;
			if vis[u as usize] { continue; }
			vis[u as usize] = true; ans = d; cnt += 1;
			if let Some(neis) = g.get(&u) {
				for &(v, w) in neis {
					if !vis[v as usize] {
						heap.push((-(d+w), v));
					}
				}
			}
		}
		if cnt == n { ans } else { -1 }
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


function networkDelayTime(times: number[][], n: number, k: number): number {
	const g: Map<number, [number, number][]> = new Map();
	for (const [u, v, w] of times) {
		if (!g.has(u)) g.set(u, []);
		g.get(u)!.push([v, w]);
	}
	const vis = new Set<number>();
	const pq: [number, number][] = [[0, k]];
	let ans = 0;
	while (pq.length) {
		pq.sort((a, b) => a[0] - b[0]);
		const [d, u] = pq.shift()!;
		if (vis.has(u)) continue;
		vis.add(u); ans = d;
		for (const [v, w] of g.get(u) ?? []) {
			if (!vis.has(v)) pq.push([d+w, v]);
		}
	}
	return vis.size === n ? ans : -1;
}

Complexity

⏰ Time complexity: O(E log N) where E is the number of edges and N is the number of nodes (for Dijkstra’s algorithm).
🧺 Space complexity: O(N + E) for the graph and visited structures.

Problem#

Solution#

Method 1 – Dijkstra’s Algorithm (BFS with Priority Queue)#

Intuition#

Approach#

Code#

Complexity#