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.)
Solution
We wish to find the shortest path from k
to all nodes in the graph.
Dijkstra's algorithm is the best approach in finding shortest path from a single source.
We will keep track of the delay time from k
to each node, and find the maximum in the end.
Implementation
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
graph = defaultdict(list)
for src, dst, time in times:
graph[src].append((time, dst))
queue = [(0, k)]
delay_time = [inf for _ in range(n+1)]
while queue:
cur_time, cur_node = heapq.heappop(queue) # pop min from min-heap
if cur_time > delay_time[cur_node]: # a shorter path exists
continue
for edge in graph[cur_node]:
new_time, new_node = edge
if delay_time[new_node] > cur_time + new_time:
delay_time[new_node] = cur_time + new_time
heapq.heappush(queue, (delay_time[new_node], new_node))
max_delay = max(delay_time)
return max_delay if max_delay != inf else -1
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorHow does merge sort divide the problem into subproblems?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!