Network Delay Time
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:
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.)
Solutions
This problem can be solved using Dijkstra’s algorithm, which is a famous algorithm for finding the shortest paths from a single source in a graph with non-negative edge weights.
public class Solution {
public int NetworkDelayTime(int[][] times, int n, int k) {
var graph = new Dictionary<int, List<(int, int)>>();
foreach (var time in times) {
if (!graph.ContainsKey(time[0])) {
graph[time[0]] = new List<(int, int)>();
}
graph[time[0]].Add((time[1], time[2]));
}
var dist = new Dictionary<int, int>();
for (int i = 1; i <= n; ++i) {
dist[i] = int.MaxValue;
}
dist[k] = 0;
var heap = new SortedSet<(int, int)>() { (0, k) };
while (heap.Count > 0) {
var node = heap.Min;
heap.Remove(node);
int d = node.Item1, nodeIdx = node.Item2;
if (d != dist[nodeIdx]) continue;
if (graph.ContainsKey(nodeIdx)) {
foreach (var pair in graph[nodeIdx]) {
int nei = pair.Item1, d2 = pair.Item2;
if (dist[nodeIdx] + d2 < dist[nei]) {
heap.Remove((dist[nei], nei));
dist[nei] = dist[nodeIdx] + d2;
heap.Add((dist[nei], nei));
}
}
}
}
int ans = 0;
foreach (var cand in dist) {
ans = Math.Max(ans, cand.Value);
}
return ans == int.MaxValue ? -1 : ans;
}
}
The time complexity of this solution is O(E log E), where E is the number of edges (or the length of times), because in the worst case we need to iterate over each edge and update the queue. The space complexity is O(N + E), where N is the number of nodes, because we need to store the graph (O(E)) and the distance of each node (O(N)).
Last updated