Domain 2MediumMEDIUM

Network Delay Time

Uses Dijkstra's algorithm with a min-heap to find shortest paths from source k, returning -1 if any node remains unreachable.

Domain: medium•Updated: 2026-08-31
#Dijkstra#Priority Queue#O(E log V)#Space O(V + E)

Problem Breakdown

We are given a directed graph where nodes represent network stations and edges represent signal transmission times. The goal is to calculate the time required for all n nodes to receive a signal starting from node k. This effectively requires finding the longest of the shortest paths (the maximum distance) among all reachable nodes in the single-source shortest path problem. If any node cannot be reached, the system fails (-1).

  • Inputs:
    • times: List of directed edges [u, v, w].
    • n: Number of nodes (labeled 1 to n).
    • k: Source node index.
  • Output: Integer representing max⁡(shortest_path(k→i))\max(\text{shortest\_path}(k \to i)) for all ii, or -1 if unreachable.

Intuition

This problem is a classic application of the Single-Source Shortest Path algorithm on a weighted graph with non-negative edge weights (w≥0w \ge 0).

  1. Why not BFS/DFS? Standard Breadth-First Search (BFS) only works for unweighted graphs or finding shortest paths in terms of hop count, ignoring the wi travel times. Depth-First Search (DFS) does not guarantee visiting nodes by increasing distance order and can get stuck exploring long paths before shorter ones are found without a priority queue.
  2. Why Dijkstra? Since edge weights are non-negative, we can greedily expand from the source node to always process the closest unvisited neighbor first using a Min-Heap (Priority Queue). This ensures that once a node is popped from the heap, its shortest distance from k has been finalized.
  3. Handling Disconnection: We must track distances for all nodes 1…n1 \dots n. If any node retains an initial value of infinity after processing, it means no path exists from k, necessitating a return of -1.

Approach

  1. Graph Representation: Construct an adjacency list where each key is a source node and the value is a list of tuples (target_node, weight). This allows efficient O(1)O(1) neighbor iteration during traversal.
  2. Initialization:
    • Create a distance array dists of size n + 1, initialized to infinity (float('inf')). The extra index accounts for the problem’s 1-based indexing (nodes 1 through n).
    • Set dists[k] = 0.
  3. Priority Queue: Initialize a min-heap with (distance, node) starting from (0, k).
  4. Dijkstra Loop:
    • While the heap is not empty:
      • Pop the element with the smallest current distance (d, u).
      • Check for stale entries (if d > dists[u], skip). This handles cases where a node was updated multiple times before being popped.
      • For each neighbor v of u: calculate potential new distance new_dist = d + w.
      • If new_dist < dists[v], update dists[v] and push (new_dist, v) to the heap.
  5. Result Extraction: Iterate through indices 11 to nn. If any node has a distance of infinity, return -1. Otherwise, compute the maximum value in the valid distances array.

Complexity Analysis

  • Time: O(Elog⁡V)O(E \log V) or more precisely O((V+E)log⁡V)O((V + E) \log V). We iterate over each edge once (EE), and heap operations take logarithmic time relative to the number of elements currently in the priority queue (bounded by edges). Given constraints N≤100N \le 100, this is highly efficient.
  • Space: O(V+E)O(V + E) required for the adjacency list, distance array, and heap storage.

Solution

import heapq
from collections import defaultdict
from typing import List

def networkDelayTime(times: List[List[int]], n: int, k: int) -> int:
    # Build adjacency list for O(1) neighbor lookup
    adj = defaultdict(list)
    for u, v, w in times:
        adj[u].append((v, w))

    # Initialize distances to infinity; source starts at 0. 
    # Size is n + 1 because nodes are labeled 1 through n.
    dists = [float('inf')] * (n + 1)
    dists[k] = 0
    
    # Min-heap stores tuples of (current_distance, node_index)
    pq = [(0, k)]
    
    while pq:
        d, u = heapq.heappop(pq)

        # If popped distance is greater than recorded shortest path, skip stale entry
        if d > dists[u]:
            continue
            
        for v, w in adj[u]:
            new_dist = d + w
            if new_dist < dists[v]:
                dists[v] = new_dist
                heapq.heappush(pq, (new_dist, v))

    # Check reachability and find max time among all nodes 1 to n
    max_time = 0
    for i in range(1, n + 1):
        if dists[i] == float('inf'):
            return -1
        
        max_time = max(max_time, dists[i])
        
    return max_time

Edge Cases Handled

  • Unreachable Nodes: The code explicitly checks dists[i] against infinity. If any node i∈[1,n]i \in [1, n] is unreachable from kk, the function returns -1. This handles disconnected subgraphs correctly.
  • Single Node Network (N=1N=1): When n=1n=1 and k=1k=1, dists[1] remains 0 (no edges exist). The loop checks index 1, finds distance is not infinity, sets max_time = max(0, 0), returning 0. This is correct as no travel time is needed for the single node to receive its own signal.
  • Zero Weights: Dijkstra handles w=0w = 0 correctly because non-negative weights are required; equal distances do not break correctness or termination order in a min-heap implementation.
  • Import Dependencies: The solution includes necessary imports (collections, typing) to ensure it runs standalone without relying on implicit environment assumptions, preventing NameErrors for defaultdict or List.