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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Network Delay Time

Number: 744

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Netflix, TikTok, Akuna Capital

Problem Description

Find the minimum time required for a signal sent from a starting node k to reach every node in a network of n nodes. The network is given as a list of directed edges with travel times. If there exists any node that cannot be reached, return -1.

Key Insights

  • This is a single-source shortest path problem on a directed graph.
  • Since all edge weights are non-negative, Dijkstra’s algorithm is well-suited for this problem.
  • Construct an adjacency list for the graph.
  • Utilize a min-heap (priority queue) to efficiently select the next node with the smallest cumulative travel time.
  • The answer is the maximum travel time among all reachable nodes; if any node is unreachable, return -1.

Space and Time Complexity

Time Complexity: O(E log V) where E is the number of edges and V is the number of nodes. Space Complexity: O(V + E) due to the adjacency list and distance storage.

Solution

We solve the problem using Dijkstra’s algorithm. First, an adjacency list is built using the input times array. A distance map (or array) records the shortest known distance from the starting node k to all other nodes, initialized to infinity except for k which is set to 0. A min-heap stores nodes prioritized by their current shortest distance.

The algorithm repeatedly extracts the node with the smallest distance from the heap. For each neighbor of the current node, it checks if a shorter path is found via the current node; if so, the neighbor’s distance is updated and it is added to the heap. Once all nodes are processed, the answer is the maximum distance from the k node. If any node remains unreachable (has distance equal to infinity), return -1.

Code Solutions

import heapq

def networkDelayTime(times, n, k):
    # Build the graph as an adjacency list
    graph = {i: [] for i in range(1, n + 1)}
    for u, v, w in times:
        graph[u].append((v, w))
    
    # Initialize distances: infinity for all nodes except the starting node k with distance 0
    dist = {i: float('inf') for i in range(1, n + 1)}
    dist[k] = 0
    # Use a heap as a priority queue storing (distance, node) pairs
    heap = [(0, k)]
    
    while heap:
        current_dist, node = heapq.heappop(heap)
        # If we have already found a better path, skip
        if current_dist > dist[node]:
            continue
        # Update the path for neighbors
        for neighbor, weight in graph[node]:
            new_dist = current_dist + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    
    # Maximum distance among all nodes represents the time taken for the signal to reach every node
    max_time = max(dist.values())
    return max_time if max_time != float('inf') else -1

# Example usage:
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2))
← Back to All Questions