We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Network Delay Time

Difficulty: Medium

Problem Description

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] = (u_i, v_i, w_i), where u_i is the source node, v_i is the target node, and w_i 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.

Key Insights

  • The problem can be modeled as a directed graph where nodes represent network nodes and edges represent the travel times.
  • Dijkstra's algorithm is suitable for finding the shortest path in a graph with non-negative edge weights.
  • A priority queue (min-heap) can be utilized to efficiently fetch the next node with the smallest accumulated travel time.
  • If after processing all reachable nodes there are still nodes not reached, it implies some nodes are unreachable, hence the result should be -1.

Space and Time Complexity

Time Complexity: O((N + E) log N), where N is the number of nodes and E is the number of edges, due to the priority queue operations. Space Complexity: O(N + E) for the graph representation and the storage of travel times.

Solution

To find the minimum time for all nodes to receive the signal, we can use Dijkstra's algorithm. We will represent the graph using an adjacency list, where each node points to its neighbors and the corresponding travel times. We will initiate a priority queue to explore the nodes starting from the source node k. We will keep track of the shortest time for each node to receive the signal. If all nodes receive the signal, we return the maximum time taken; otherwise, we return -1 if any node is unreachable.

Code Solutions

import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    # Create an adjacency list for the graph
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    # Min-heap to store (time, node)
    min_heap = [(0, k)]  # starting with time 0 at node k
    # Dictionary to store the shortest time to reach each node
    shortest_time = {i: float('inf') for i in range(1, n + 1)}
    shortest_time[k] = 0
    
    while min_heap:
        current_time, node = heapq.heappop(min_heap)
        
        # Only process if the current time is less than the recorded shortest time
        if current_time > shortest_time[node]:
            continue
        
        # Explore neighbors
        for neighbor, travel_time in graph[node]:
            time = current_time + travel_time
            # If found a shorter time to neighbor
            if time < shortest_time[neighbor]:
                shortest_time[neighbor] = time
                heapq.heappush(min_heap, (time, neighbor))
    
    # Get the maximum time from the shortest_time dictionary
    max_time = max(shortest_time.values())
    return max_time if max_time < float('inf') else -1
← Back to All Questions